组合数的性质和定理

· · 个人记录

从m个物品里选出n个的方案数，记作C_m^n，即为组合数

组合数通项公式

C_m^n=\frac{m!}{n! * (m-n)!}

证明

  从m个不同的数中选出n个数组成一个排列，第一个位置上的数有m种取法，第二个位置上的数有m-1种取法，第三个位置上的数有m-2种取法…共有\frac{m!}{(m-n)!}种。
  由于我们对于顺序没有要求，假设取出了n个数，第一个位置上有n种放法，第二个位置上有n-1种放法…所以我们刚才得到的答案还要除一个n!

组合数递推公式

C_m^n=C_{m-1}^n+C_{m-1}^{n-1}

证明

  从 m 个不同的数中取 n 个，第 m 个数如果取的话有

## 性质1 $$C_m^n=C_m^{m-n}$$ ### 证明   显然从 $m$ 个物品里选 $n$ 个和从 $m$ 个物品里选 $m-n$ 个丢掉的方案数是一样的。 ## 性质2 $$C_{m+n+1}^{n}=\sum\limits_{i=0}^{n}C_{m+i}^{i}$$ ### 证明   用组合数的递推公式   $∵C_m^0=C_{m+1}^0=1

  ∴\ \ C_m^0+C_{m+1}^{1}+C_{m+2}^{2}+…+C_{m+n}^{n}
   =C_m^{1}+C_{m+1}^{1}+C_{m+2}^{2}+…+C_{m+n}^{n}
   =C_{m+2}^{1}+C_{m+2}^{2}+…+C_{m+n}^{n}
   =C_{m+n+1}^{n}

性质3

C_m^n * C_n^r=C_m^r * C_{m-r}^{n-r}

证明

  用组合数的通项公式
   C_m^n * C_n^r
  =\frac{m!}{n!(m-n)!} * \frac{n!}{r!(n-r)!}
  =\frac{m!}{r!(m-r)!} * \frac{(m-r)!}{(m-n)!(n-r)!}
  =C_m^r * C_{m-r}^{n-r}

性质4(二项式定理)

\sum\limits_{i=0}^mC_m^i=2^m

证明

  C_m^i 代表一个 m 位二进制数有 i 个 0 的情况下的数量，那么这个和就是 m 位二进制数的数量了。
  推广一下这个二项式定理:

\sum\limits_{i=0}^m C_m^i * x^i=(x+1)^m

证明

(x+1)^m=(x+1)(x+1)(x+1)···

  假设说有 i 次方项，选择的 i 个 x 从 m 个括号中来，有 C_m^i 种方案，所以 x^i 项的系数是 C_m^i。

性质5

C_m^0-C_m^1+C_m^2-…\pm C_m^m=0

证明

  若 m 为奇数，由性质 1 可知正确。
  若 m 为偶数，显然 C_{m-1}^0=C_m^0=1 且 C_{m}^{m}=C_{m-1}^{m-1}。
  由递推公式得：
   C_m^0-C_m^1+C_m^2-…+ C_m^m
  =C_{m-1}^0-(C_{m-1}^0+C_{m-1}^1)+C_{m-1}^{1}+C_{m-1}^2-…+C_{m-1}^{m-1}
  =0

性质6

C_m^0+C_m^2+C_m^4+…=C_m^1+C_m^3+C_m^5+…=2^{m-1}

证明

C_m^0+C_m^1+C_m^2+…+C_m^m=2^m C_m^0-C_m^1+C_m^2-…+ C_m^m=0

  两式相加相减可知原式成立。

性质7

C_{m+n}^r=C_m^0 * C_n^r+C_m^1 * C_n^{r-1}+…+C_m^r * C_n^0

证明

  考虑选出的 r 个物品在前 m 个物品有几个，在后 n 个物品里有几个即可。
  特别的:

C_{m+n}^n=C_m^0 * C_n^0+C_m^1 * C_n^1+…+C_m^m * C_n^m

  这个是根据性质 1 变形得到的。

性质8

n * C_m^n=m * C_{m-1}^{n-1}

证明

  由通项公式得
   n * C_m^n
  =n * \frac{m!}{n!(m-n)!}
  =\frac{m!}{(n-1)!(m-n)!}
  =m * \frac{(m-1)!}{(n-1)!(m-n)!}
  =m * C_{m-1}^{n-1}

性质9

\sum\limits_{i=1}^{n}C_n^i * i=n * 2^{n-1}

证明

   \sum\limits_{i=1}^{n}C_n^i * i
  =\sum\limits_{i=1}^n\frac{n!}{i!(n-i)!} * i
  =\sum\limits_{i=1}^n\frac{n!}{(i-1)!(n-i)!}
  =\sum\limits_{i=1}^n\frac{(n-1)!}{(i-1)!(n-i)!} * n
  =\sum\limits_{i=0}^{n-1}C_n^i* n
  =n* 2^{n-1}

性质10

\sum\limits_{i=1}^nC_n^i* i^2=n*(n+1)* 2^{n-2}

证明

   \sum\limits_{i=1}^nC_n^i* i^2
  =\sum\limits_{i=1}^{n}\frac{n!}{i!(n-i)!}* i^2
  =\sum\limits_{i=1}^{n}\frac{(n-1)!}{(i-1)!(n-i)!}* i * n
  =\sum\limits_{i=0}^{n-1}\frac{(n-1)!}{i!(n-i-1)!}* (i+1)* n
  =\sum\limits_{i=0}^{n-1}C_{n-1}^i*(i+1)* n
  =(\sum\limits_{i=0}^{n-1}C_{n-1}^i* i+ \sum\limits_{i=0}^{n-1}C_{n-1}^i)* n
  =(2^{n-2}* (n-1)+2^{n-1})* n
  =(2^{n-2}* (n-1)+2^{n-2}* 2)* n
  =2^{n-2}* (n+1)* n
  =n*(n+1)* 2^{n-2}

性质11

\sum\limits_{i=0}^{n}(C_n^i)^2=C_{2n}^n

证明

  从两堆物品(每堆都有 n 个)中一共选择 n 个物品，有 C_{2n}^n 种方案，也是从第一堆物品中选择 i 个，从第二堆物品中选择 n-i 个的方案，根据乘法原理乘起来，因为 C_n^i=C_{n}^{n-i}，得到

\sum\limits_{i=0}^{n}(C_n^i)^2