叶卢庆的博客

从计数的角度理解组合数的若干性质

在此,我们从计数的角度来理解组合数的若干性质.组合数${n\choose k}$的意思,就是从$n$个不同的物体里选取$k$个物体形成一组,在不计$k$个物体的排列顺序的条件下,所有可能的组形成的集合的元素个数.也就是说,两个组,只要它们拥有共同的物体,即便物体的排列顺序不同,这两个组也会被视为同一个组.

性质1:\begin{equation}
\label{eq:1}
{n\choose k}=\frac{n!}{(n-k)!k!}.
\end{equation}


证明:首先,根据乘法原理,$\frac{n!}{(n-k)!}=n(n-1)\cdots(n-k+1)$是从$n$个不同物体里选取$k$个物体之后,再把$k$个物体按顺序排成一列,所有可能的列形成的集合的元素个数.也就是说,若有两列,它们都有$k$个物体,且这$k$个物体相同,但是这$k$个物体的排列顺序不同,则这两列会被看作集合里不同的元素.对于集合里的任意一个元素来说,“有相同物体”这个关系是一个等价关系.由乘法原理,和集合里任意一个元素拥有相同物体的元素共有$k!$个(包括自己).由于组合是不考虑顺序的,因此一个组合就是一个等价类,一个等价类也就是一个组合.而等价类共有$\frac{n!}{(n-k)!k!}$个.这样就得到了组合数的公式.


性质2:$$
{n\choose k}=\frac{n-k+1}{k}{n\choose k-1}.
$$


证明:${n\choose k-1}$是从$n$个不同物体里选取$k-1$个物体形成一组的种数.而${n\choose k}$是从$n$个不同物体里选取$k$个物体形成一组的种数.从$n$个不同物体里选取$k$个物体形成一组,可以分为两步,第一步是从$n$个物体里选取$k-1$个物体形成一组,再在剩下的$n-k+1$个物体里选取$1$个元素,放进这组里.因此有人会说答案是
$$
{n\choose k}=(n-k+1){n\choose k-1}.
$$
然而,他们忽略了这样一个事情.乘法原理有个微妙的地方.最简单地说,完成一件事情有2步,第一步有$a$种方法,第二步有$b$种方法,则完成这件事情共有$ab$种方法.但是要注意的是,虽然完成这件事情有$ab$种方法,但是完成这件事情得到的结果不一定有$ab$个.因为不同的完成方法可能得到相同的结果.为了确保完成的结果也有$ab$个,必须证明不同的完成方法有不同的结果.

先从$n$个不同物体里选取$k-1$个物体形成一组,再从剩下的$n-k+1$个物体里选取$1$个物体放进组里,最终得到的所有的组形成的集合是一个多重集,该多重集里每个元素的重数为$k$.这是因为,最终得到的组里的$k$个物体中,每个物体都可能是从剩下的$n-k+1$个元素里选取过来的.因此,把这个多重集里重复的元素删去,形成的集合的元素个数才是${n\choose k}$.因此我们有
$$
{n\choose k}=\frac{(n-k+1)}{k}{n\choose k-1}.
$$


性质3:$$
{n\choose m}=\frac{n}{n-m}{n-1\choose m}.
$$


证明:从$n$个不同物体里选取$m$个物体形成一组,可以分成两种情况.固定$n$个物体里的某个物体$A$.第一种情况是,从$n$个物体中除$A$外的$n-1$个物体里选取$m$个物体形成一组.第二种情况是,$A$被选进去了,然后再从除$A$外的$n-1$个物体里选取$m-1$个物体,连同$A$形成一组.于是
$$
{n\choose m}={n-1\choose m}+{n-1\choose m-1}.
$$
而由第二个性质,${n-1\choose m}=\frac{n-m}{m}{n-1\choose m-1}$,因此
$$
{n\choose m}={n-1\choose m}+\frac{m}{n-m}{n-1\choose m}=\frac{n}{n-m}{n-1\choose m}.
$$