[组合数学] 不相邻的组合数

一、从排成一行的 n 个球中选出互不相邻的 r 个球，有多少种取法？

  • n < 2r-1 时，取法为 0 种。例如 4 个球里取 3 个互不相邻的球，找不到这样的组合。
  • n \geq 2r-1 时，取法为 C_{n-r+1}^r 种。这里考虑逆向思维，先从 n-r+1 个球中任取 r 个球，取法为 C_{n-r+1}^r 种，然后再另外拿 r-1 个球插到那 r 个球的 r-1 个空位中，这样使得我们原本取出的 r 个球都互不相邻，并且最后总球数为 n 个。不难验证逆向思维得出的情况与正常考虑的情况是一一对应的，故我们可以得到上面的结论。（临界情况： n=2r-1 时，比如 5 个里取 3 个， 7 个里取 4 个，此时恰好只有 C_{n-r+1}^r = C_r^r = 1 种取法）

二、从围成一圈的 n 个球中选出互不相邻的 r 个球有多少种取法？

  • n < 2r 时，取法为 0 种。例如 4 个球围成一圈，选互不相邻的 3 个球，找不到这样的组合。
  • n \geq 2r 时，取法为 \frac{nC_{n-r}^r}{n-r} 种。首先对球进行编号 1 到 n ，对于任何可行的组合，都只有两种情况，即包含 1 号球的和不包含 1 号球的：
    • 包含 1 号球：首先选出 1 号球，然后需要从 3 号球到 n-1 号球取出 r-1 个互不相邻的球，根据上面那道题的结论，取法为 C_{n-3-(r-1)+1}^{r-1} = C_{n-r-1}^{r-1} 种
    • 不包含 1 号球：我们需要从 2 号球到 n 号球取出 r 个互不相邻的球，根据上面那道题的结论，取法为 C_{n-1-r+1}^{r} = C_{n-r}^{r} 种

因此，当 n \geq 2r 时，取法总数为 C_{n-r-1}^{r-1} + C_{n-r}^{r} = \frac{n C_{n-r}^r}{n-r} 种。（临界情况：当 n=2r 时，例如 4 个里取 2 个，共有 \frac{2rC_{r}^r}{r} = 2 种）

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。