组合意义的解释

组合数学 数学

这篇笔记主要记录了一些组合数的公式, 并用它们的组合意义来解释这些公式.

1. $C(n,r)=C(n,n-r)$.
   理解 :
   当你在 $n$ 个数中取出 $r$ 个数时, 就相当于取出了剩下的 $n-r$ 个数, 所以两者的方案数时相同的.

2. $C(n,r)=C(n-1,r-1)+C(n-1,r)$.
   理解 :
   在 $n$ 个数中取 $r$ 个数可以分为两类方案,
   第一类取第 $n$ 个数, 那么就要在前 $n-1$ 个数中取 $r-1$ 个数;
   第二类不取第 $n$ 个数, 那么就要在前 $n-1$ 个数中取足 $r$ 个数, 再根据加法法则, 把两者的方案数相加即可.

   有了这个公式, 我们就可以像推杨辉三角一样递推组合数了.

3. $C(n+r+1,n+1)=C(n,n)+C(n+1,n)+\cdots+C(n+r,n)$.
   理解 :
   设在 $[1,n+r+1]$ 中取 $n+1$ 个数的某一个组合为 $a_1,a_2,\cdots,a_{n+1}$,
   且 $a_1<a_2<\cdots<a_{n+1}$, 可以分为以下情况讨论 :
   (1) $a_{n+1}=n+1$, 那么就在 $[1,n]$ 中取 $n$ 个数, 方案数为 $C(n,n)$;
   (2) $a_{n+1}=n+2$, 那么就在 $[1,n+1]$ 中取 $n$ 个数, 方案数为 $C(n+1,n)$;
   $\vdots$
   (r+1) $a_{n+1}=n+r+1$, 那么就在 $[1,n+r]$ 中取 $n$ 个数, 方案数为 $C(n+r,n)$;
   在根据加法法则, 把所有方案数加起来就行了.

4. $C(n,l)*C(l,r)=C(n,r)*C(n-r,l-r)$.
   理解 :
   等式左边的式子可以理解为 先在 $n$ 个人中选出 $l$ 个人, 在从这 $l$ 个人中选出 $r$ 个人的方案数;
   右边的式子可以理解为 现在 $n$ 个人中选出 $r$ 个人, 再以这 $r$ 个人为基础, 在剩下的 $n-r$ 个人中选出 $l-r$ 个人;
   可以发现, 这两个式子实质上表示的是一个东西, 所以它们的方案数是一样的.

5. $C(m,0)+C(m,1)+C(m,2)+\cdots+C(m,m)=2^m$.
   理解 :
   $2^m$ 表示的是 有 $m$ 个数, 每个数选或不选, 总的方案数.
   那么对这个方案进行分类, 就可以分成
   没有选数, 方案数为 $C(m,0)$;
   选了 1 个数, 方案数为 $C(m,0)$;
   $\vdots$
   选了 m 个数, 方案数为 $C(m,m)$;
   再根据加法法则, 把方案数加起来, 就可以得到等式左边了.

6. $C(m,0)-C(m,1)+C(m,2)-C(m,3)+\cdots \pm C(m,m)=0$
   理解 :
   我第一眼看到这个式子的时候是一脸懵逼的....
   我们可以移个项, 就变成了 (这里假设 $m$ 为奇数)
   

   $$C(m,0)+C(m,2)+\cdots+C(m,m-1) = C(m,1)+C(m,3)+\cdots+C(m,m)$$
   这时, 我们可以看出来这个式子表达的意思是 : 在 $m$ 个元素中取奇数个元素的方案数 等于 取偶数个元素的方案数, 也就是说, 取奇数个元素的方案与取偶数个元素的方案一一对应.

   考虑对于一个元素 $a$, 可以把所有方案分为两类 : 含 $a$ 的 和 不含 $a$ 的.
   我们把一个方案看作是一个递增的序列.

   对于所有长度为奇数且含 $a$ 的序列, 把 $a$ 删掉, 就可以得到所有长度为偶数且不含 $a$ 的序列;
   对于所有长度为奇数且不含 $a$ 的序列, 把 $a$ 加上, 就可以得到所有长度为偶数且含 $a$ 的序列;
   所以我们可以得到, 长度为奇数的序列与长度为偶数的序列一一对应, 所以它们的方案数自然也是相等的, 等式成立.

7. $C(m+n,r)=C(m,0)*C(n,r)+C(m,1)*C(n,r-1)+\cdots+C(m,r)*C(n,0)$.
   理解 :
   等式左边表示在 $m+n$ 个数里取 $r$ 个数, 那么可以将方案分类,
   在 $m$ 中取 $0$ 个, $n$ 中取 $r$ 个;
   在 $m$ 中取 $1$ 个, $n$ 中取 $r-1$ 个;
   $\vdots$
   在 $m$ 中取 $r$ 个, $n$ 中取 $0$ 个;
   加法法则, 方案数相加即可.

8. $C(m+n,n)=C(m,0)*C(n,0)+C(m,1)*C(n,0)+\cdots+C(m,n)*C(n,n)$.
   理解 :
   这个式子其实就是 公式1 与 公式7 的结合体, 当 $r=m$ 时, 把 公式1 代入 公式7 就可以得到.