性质 1 以下组合恒等式成立:
\(1\). \(\dbinom{n}{k}=\dbinom{n}{n-k}\).
\(2\). \(\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1}\).
\(3\). \(\dbinom{n}{k}=\dfrac{n}{k}\dbinom{n-1}{k-1}\).
证明:虽然可以代入组合数公式 \(\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}\) 暴力验证, 但我们还是希望 “用组合的观点”理解它们.
- 我们知道, \(\dbinom{n}{k}\) 是从 \([n]\) 当中挑选 \(k\) 个元素的方法数; 若挑选了某 \(k\)个, 则剩下 \((n-k)\) 个元素未被挑选, 这自然给出 “从 \(n\) 个元素中挑选 \(k\) 个” 与 “从 \(n\) 个元素挑选 \(n-k\) 个” 之间的一一对应, 从而得证.
- 对于 \([n]\) 的 \(k\) 元子集 \(A\), 则要么 \(1 \in A\), 要么 \(1 \notin A\). 若 \(1 \notin A\), 则需要从 \([n] \backslash\{1\}\) 中挑选 \(k\) 个; 若 \(1 \in A\), 只需再从 \([n] \backslash\{1\}\) 中挑选 \(k-1\) 个. 从而得证.
- 最后看第三个. 设想某个班有 \(n\) 个学生, 从中选出 \(k\) 个人参加某小组活动, 并在这 \(k\) 人当中选出 1 名组长, 则安排方案有多少种. 一方面,先选出参加活动的 \(k\) 人, 共 \(\dbinom{n}{k}\) 种选法, 然后再从 \(k\) 人当中选出组长,因此总共 \(k\dbinom{n}{k}\) 种方案; 另一方面, 也可以先从 \(n\) 个人当中指定组长,再从剩余 \((n-1)\) 人当中选出 \((k-1)\) 名组员, 因此共有 \(n\dbinom{n-1}{k-1}\) 种活动方案. 因此 \(k\dbinom{n}{k}=n\dbinom{n-1}{k-1}\), 得证.
性质 2 (Vandermonde 卷积公式) 对于正整数 \(m, n\), 成立
\[\dbinom{m+n}{k}=\sum_{\substack{i+j=k \\ i, j \geq 0}}\dbinom{m}{i}\dbinom{n}{j} . \]证明：直接代入组合数公式 \(\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}\) 并不能轻易证明此式; 而在组合的观点下, 它显然成立. 设想有 \(m\) 个男生与 \(n\) 个女生当中挑选 \(k\) 个人,一方面, 显然有 \(\dbinom{m+n}{k}\) 种挑选方法; 另一方面, 考虑选出来的 \(k\) 人当中男女各多少, 若选出 \(i\) 个男生 \(j\) 个女生, 则这样的取法有 \(\dbinom{m}{i}\dbinom{n}{j}\) 种, 再让 \(i, j\)取遍 \(\{(i, j) \mid i+j=k, i, j \geq 0\}\) 即可.
可见, 适当构造组合模型, 并用不同的方法计数, 能够得到不平凡的恒等式.性质 3 关于 \(n\) 个未知数 \(x_1, \ldots, x_n\) 的不定方程
\[\left\{\begin{array}{l} x_1+x_2+\cdots+x_n=k \\ x_i \in\{0,1\}, \quad \forall i=1, \ldots, n \end{array}\right. \]有 \(\dbinom{n}{k}\) 组不同的解.
这是显然的. 为满足此方程, \(n\) 个未知数里面必然有 \(k\) 个取值为 \(1\) ; 这相当于从 \(n\) 个未知数里挑选 \(k\) 个.
性质 4 关于 \(n\) 个未知数 \(x_1, \ldots, x_n\) 的不定方程
\[\left\{\begin{array}{l} x_1+x_2+\cdots+x_n=k \\ x_i \in \mathbb{Z}_{\geq 0}, \quad \forall i=1, \ldots, n \end{array}\right. \]有 \(\dbinom{k+n-1}{k}\) 组不同的解.
证明：这是经典的 “隔板插球” 问题. 设想有 \(n\) 个不同的箱子与 \(k\) 个相同的球,将这 \(k\) 个球放入这 \(n\) 个箱子, 若第 \(i\) 个箱子里放入 \(x_i\) 个球, 则 \(\left(x_1, \ldots, x_n\right)\) 是上述不定方程的一组解. 容易验证该不定方程的解与将球放入箱子的方法一一对应, 从而解的个数等于将球放入箱子的方法数.
为了把球放到箱子里, 先把这 \(k\) 个球从左往右排成一排, 在相邻两球的间隙处插入隔板, 用 \((n-1)\) 个隔板把球分成 \(n\) 堆, 这 \(n\) 堆从左往右依次放入 \(n\) 个箱子里. 于是, 只需考虑有多少种插入隔板的方式. 将 \(k\) 个球与 \((n-1)\) 个隔板都视为物体, 共有 \((k+n-1)\) 个物体从左向右排成一排, 占据 \((k+n-1)\) 个位置. 这 \((k+n-1)\) 个位置里面, 有 \(k\) 个位置是球, 因此共有 \(\dbinom{k+n-1}{k}\) 种情形.
“隔板插球”与 “箱子放球”一一对应，具体来说，把 $k$ 个球放入 $n$ 个箱子里对应于 $n-1$ 个隔板插入 $k$ 个球的k+1个缝隙中。关于得到 \(\dbinom{k+n-1}{k}\) 的过程，我们通常有两种等价的理解办法：
\(1.\) 由于球和球之间和板和板之间都是相同的，所以只需在 \((k+n-1)\) 个位置里选出 \(k\) 个球的位置，剩下全部放板即可，共有 \(\dbinom{k+n-1}{k}\) 种方式；
\(2.\) \((k+n-1)\) 个位置全排列，然后去掉因为球和球相同以及板和板相同而多算的方式数，这样得到的方法数为 \(\dfrac{(k+n-1)!}{k!~(n-1)!} = \dbinom{k+n-1}{k}\).
习题 5 从 \(\{1,2, \ldots, n\}\) 中选出 \(r\) 个不同的整数, 要求这 \(r\) 个整数中的任何两个都不相邻. 则符合要求的选法有多少种?
解： 将选中的 \(r\) 个整数视为隔板, 未选中的整数视为球, 则 “任何两个选中的整数都不相邻” 即任何两个隔板都不能紧挨着, 这当且仅当任何两个隔板之间都必有球. 同上一题, 考虑 “隔板插球” 与 “箱子放球” 的一一对应, 从而只需考虑 \((r+1)\) 个不同的箱子当中, 除了第 \(1\) 个箱子与最后一个箱子之外,其余 \((r-1)\) 个箱子里都至少有 \(1\) 个球的情形. 于是, 不妨先将第 \(2,3, \ldots, r\)个箱子里各放 \(1\) 个球, 然后还剩下 \((n-r)-(r-1)=(n-2 r+1)\) 个球.之后就转化为把 \((n-2 r+1)\) 个球放入 \((r+1)\) 个箱子里的问题, 因此共有 \(\binom{(n-2 r+1)+(r+1)-1}{n-2 r+1}=\binom{n-r+1}{r}\) 种方案.
另解： 除了把问题强行转化为 \(1.1.4\) , 我们还有更简洁的方法. 依然将选中的数字视为隔板, 未选中的数字视为球. 则一共有 \((n-r)\) 个球. 注意到隔板的位置一定是在相邻两球之间, 或者第一个球的左侧, 或者最后一个球的右侧,一共 \((n-r+1)\) 个可供插隔板的 “空隙”. 任何两个隔板不能紧挨着, 相当于每个 “空隙” 至多被插入一个隔板. 即 \((n-r+1)\) 个空隙当中的 \(r\) 个空隙里面有隔板, 故共有 \(\binom{n-r+1}{r}\) 种情形.
标签：隔板,排列,1.1,组合,箱子,dbinom,ldots,个球 From： https://www.cnblogs.com/Pizixsir-Math/p/18294700习题 \(5\) 实际上给出了性质 4 中把条件 “ \(x_i \in \mathbb{Z}_{\geq 0}, \forall i=1, \ldots, n\) ” ，改为“ \(x_i \in \mathbb{Z}_{\geq m}, \forall i=1, \ldots, n,\forall m\geq 0\) ” 的情形的解决办法。