不相邻问题

不相邻问题

文章目录

• 链式不相邻问题：
• • 问题
  • 解析
• 环形不相邻问题
• • 问题
  • 解析

链式不相邻问题：

问题

有n个球排成一列，从中取出m个不相邻的球，问有多少种解法。

解析

这个问题有公式，我的推导如下：

n个球取m个不相邻的球相当于将n-m个球分为m+1份，除了第一份和最后一份可以没有球，其他都要有一个球。先给中间m-1份每份一个球，问题变为：

n-m-(m-1)个球放入m+1个盒子，盒子可以没有球。用插板法可以得出：
a n s = C n − m + 1 m ans=C_{n-m+1}^{m} ans=Cn−m+1m​

环形不相邻问题

问题

有n个球排成一个环，从中取出m个不相邻的球，问有多少种解法。

解析

对付未知问题最好的方法是把它变为已知问题。

先考虑一个球，假定它必须选，则它左右都不能选，问题变为n-3个球排成一列，从中取出m-1个不相邻的球，有 C n − m − 1 m − 1 C_{n-m-1}^{m-1} Cn−m−1m−1​种选法。

再假定它必须不选，则问题变为n-1个球排成一列，从中取出m个不相邻的球，有 C n − m m C_{n-m}^{m} Cn−mm​种选法。

最后，总共有 C n − m − 1 m − 1 + C n − m m C_{n-m-1}^{m-1}+C_{n-m}^{m} Cn−m−1m−1​+Cn−mm​