排列组合十一个性质公式及证明，错排数公式及证明
排列组合十一个性质公式及证明，错排数公式及证明
排列组合是数学中的一个重要概念，广泛应用于概率论、统计学等领域。本文详细介绍了排列组合的十一个性质公式及其证明，以及错排数的公式和证明。这些内容对于深入理解排列组合的原理和应用具有重要参考价值。
排列数
从n个物品中不放回地依次选m个物品，考虑顺序，有多少种方案，记作$A_n^m$
$$A_n^m=\frac{n!}{(n-m)!}$$
组合数
从n个物品中不放回地依次选m个物品，不考虑顺序，有多少种方案，记作$C_n^m$
$$C_n^m=\frac{n!}{m!*(n-m)!}$$
求组合数常用公式
定义式
$$C_n^m=\frac{n!}{m!*(n-m)!}$$
当n, m很大时，预处理阶乘和逆元，预处理$O(n)$，求组合数$O(1)$
递推式
$$C_n^m=\frac{n!}{m!(n-m)!}=\frac{n!}{(m-1)!(n-m+1)!}\frac{n-m+1}{m}=C_n^{m-1}\frac{n-m+1}{m}$$
杨辉三角
$$C_n^m=\frac{n!}{m!(n-m)!}=\frac{(n-1)!(n-m+m)}{m!*(n-m)!}$$
$$=\frac{(n-1)!(n-m)}{m!(n-m)!}+\frac{(n-1)!m}{m!(n-m)!}$$
$$=\frac{(n-1)!}{m!(n-m-1)!}+\frac{(n-1)!}{(m-1)!(n-m)!}$$
$$=C_{n-1}^m+C_{n-1}^{m-1}$$
当模数不是质数的时候，预处理$O(n^2)$，求组合数$O(1)$
组合数常用性质及证明
性质一
$$C_n^m=C_n^{n-m}$$
证明：
法一：利用组合数意义理解
在n个当中选m个，相当于在n个当中不选$n-m$个
法二：公式表示
$$C_n^m=\frac{n!}{m!*(n-m)!}$$
$$C_n^{n-m}=\frac{n!}{(n-m)!(n-(n-m))!}=\frac{n!}{m!(n-m)!}$$
�性质二
$$C_{n+m+1}^m=\sum_{i=0}^mC_{n+i}^i$$
证明：
利用画图以及杨辉三角得证
性质三
$$C_n^mC_m^r=C_n^rC_{n-r}^{m-r}$$
证明：
法一：利用组合数意义理解
在n个当中选m个，再在选出的m个当中选r个
相当于在n个当中选r个，再在剩下的$n-r$个中选还需要的$m-r$
法二：公式推导
$$C_n^mC_m^r=\frac{n!}{m!(n-m)!}\frac{m!}{r!(m-r)!}=\frac{n!m!}{m!r!(n-m)!(m-r)!}$$
$$=\frac{n!}{r!(n-m)!(m-r)!}=\frac{n!(n-r)!}{r!(n-m)!(m-r)!(n-r)!}$$
$$=\frac{n!}{r!(n-r)!}\frac{(n-r)!}{(m-r!)*(n-m)!}\ \ \ \ \ {(n-r)-(m-r)=n-m}$$
$$=C_n^r*C_{n-r}^{m-r}$$
性质四(二项式定理)
$$\sum_{i=0}^n{C_n^i*x^i}=(1+x)^n$$
$$\sum_{i=0}^nC_n^i=2^n\ \ \ (x=1)$$
证明：
组合数意义理解
$(1+x)^n=(1+x)(1+x)...*(1+x)$，n个$(1+x)$相乘
$(1+x)$在乘法中的贡献相当于要么选1，要么选x
有i个$(1+x)$中选x，产生的贡献就是$x^i$，剩下的$n-i$个$(1+x)$，产生的贡献是1
在n个中任意选i个，相当于$C_n^i$
性质五
$$\sum_{i=0}^n{(-1)^i*C_n^i}=0$$
证明：
①：若n为奇数
则$\sum_{i=0}^n$共有$n+1$项（偶数项），而$(-1)^iC_n^i=(-1)^iC_n^{n-i}$
因为n为奇数，所以当i为奇数时，$n-i$为偶数，当i为偶数时，$n-i$为奇数
所以$i, n-i$奇偶性不同，那么$(-1)^i+(-1)^{n-1}$相当于$(-1)^{奇数次方}+(-1)^{偶数次方}=0$
$(-1)^i*C_n^i+(-1)^{n-i}*C_n^{n-i}=0$
偶数项刚好每一对可以相互抵消，所以性质显然成立
②：若n为偶数
$(-1)^0=(-1)^n=1$，先把$i=0, i=n$的情况拆出来，用杨辉三角展开中间项
$$\sum_{i=0}^n{(-1)^iC_n^i}=C_n^0+C_n^n+\sum_{i=1}^{n-1}{(-1)^i(C_{n-1}^i+C_{n-1}^{i-1})}$$
$$C_n^0+C_n^n+\sum_{i=0}^{n-2}{(-1)^{i+1}C_{n-1}^i}+\sum_{i=1}^{n-1}{(-1)^iC_{n-1}^i}$$
把前一个求和加上$(-1)^nC_{n-1}^{n-1}$一项，后一个求和加上$(-1)^0C_{n-1}^0$
$$C_n^0+C_n^n+\sum_{i=0}^{n-1}{(-1)^iC_{n-1}^i}-C_{n-1}^{n-1}+\sum_{i=1}^{n-1}{(-1)^iC_{n-1}^i}-C_{n-1}^0$$
注意$n-1$为奇数，奇数情况已经证明了，故这两个公式直接等于0，删掉，原式转化为
$$C_n^0+C_n^n-C_{n-1}^0-C_{n-1}^{n-1}=0$$
性质六
$$C_n^0+C_n^2+...=C_n^1+C_n^3+...=2^{n-1}$$
证明：
用杨辉三角公式暴力展开寻找规律
①假设n为奇数
$$C_n^0+C_n^2+...+C_n^{n-1}=C_{n-1}^0+C_{n-1}^1+C_{n-1}^2+C_{n-1}^3+C_{n-1}^4+...+C_{n-1}^{n-2}+C_{n-1}^{n-1}$$
$$C_n^1+C_n^3+...+C_n^n=C_{n-1}^0+C_{n-1}^1+C_{n-1}^2+C_{n-1}^3+...+C_{n-1}^{n-1}+C_{n-1}^n$$
发现每一项都是相等的，第二个式子多出来的$C_{n-1}^n=0$，所以相等得证
又根据性质四$\sum_{i=0}^nC_n^i=2^n$，前两个式子相加刚好等于$\sum_{i=0}^nC_n^i$，又相等，$/2$即为$2^{n-1}$
②假设n为偶数
$$C_n^0+C_n^2+...+C_n^n=C_{n-1}^0+C_{n-1}^1+C_{n-1}^2+C_{n-1}^3+C_{n-1}^4+...+C_{n-1}^{n-1}+C_{n-1}^{n}$$
$$C_n^1+C_n^3+...+C_n^{n-1}=C_{n-1}^0+C_{n-1}^1+C_{n-1}^2+C_{n-1}^3+...+C_{n-1}^{n-2}+C_{n-1}^{n-1}$$
仍然两两对应相等，第一个式子多出来的$C_{n-1}^n=0$，后面的方法与奇数情况一样，不赘述
性质七
$$C_{n+m}^r=\sum_{i=0}^{min(n,m,r)}{C_n^i*C_m^{r-i}}$$
$$C_{n+m}^n=C_{n+m}^m=\sum_{i=0}^{min(n,m)}{C_n^i*C_m^i},(r=n||r=m)$$
证明：
用组合数意义理解
把$n+m$个分成n个一组，m个一组，总共选r个，相当于n个中选i个，m个中选$r-i$个
性质八
$$mC_n^m=nC_{n-1}^{m-1}$$
证明：
$$mC_n^m=m\frac{n!}{m!(n-m)!}=n\frac{(n-1)!}{(m-1)!(n-m)}=nC_{n-1}^{m-1}$$
性质九
$$\sum_{i=0}^n{C_n^ii}=n2^{n-1}$$
证明：
$$\sum_{i=0}^n{C_n^ii}=\sum_{i=1}^n{\frac{n!}{i!(n-i)!}i}=\sum_{i=1}^n\frac{n!}{(i-1)!(n-i)!}$$
$$=\sum_{i=1}^n{n*\frac{(n-1)!}{(i-1)!(n-i)!}}=n\sum_{i=1}^nC_{n-1}^{i-1}=n*\sum_{i=0}^{n-1}C_{n-1}^i=n*2^{n-1}$$
由性质四可知，$\sum_{i=0}^nC_n^i=2^n,\sum_{i=0}^{n-1}C_{n-1}^i=2^{n-1}$
性质十
$$\sum_{i=0}^n{C_n^ii^2}=n(n+1)*2^{n-2}$$
证明：
利用性质九
$$\sum_{i=0}^n{C_n^ii^2}=\sum_{i=0}^n{\frac{n!}{i!(n-i)!}i(i-1+1)}$$
$$=\sum_{i=0}^n{\frac{n!}{i!*(n-i)!}i+\frac{n!}{i!(n-i)!}i(i-1)}$$
$$=\sum_{i=0}^n{C_n^ii}+\sum_{i=1}^n{\frac{n!}{(i-1)!(n-i)!}*(i-1)}$$
$$=n2^{n-1}+n\sum_{i=1}^n{\frac{(n-1)!}{(i-1)!(n-i)!}(i-1)}$$
$$=n2^{n-1}+n\sum_{i=1}^n{C_{n-1}^{i-1}(i-1)}=n2^{n-1}+n*\sum_{i=0}^{n-1}{C_{n-1}^i*i}$$
$$=n2^{n-1}+n(n-1)2^{n-2}=(n2+n*(n-1))2^{n-2}=n(n+1)*2^{n-2}$$
性质十一
$$\sum_{i=0}^n{(C_n^i)^2}=C_{2*n}^n$$
证明：
根据性质七易证
$$\sum_{i=0}^n{(C_n^i)^2}=\sum_{i=0}^n{C_n^iC_n^{n-i}}=C_{n+n}^n=C_{2n}^n$$
错排数
把n个分别写有1-n的球放进n个固定的分别写有1-n的盒子里，每个盒子里正好有一个球且盒子上的数字与盒中球的数字都不相同的方案数，记作$D(n)$
递推式：
$$D(n)=(n-1)*(D(n-1)+D(n-2))\ \ \ \ \ D(1)=0,D(2)=1$$
证明：
第一个盒子有$n-1$种球可以放（除了一号球），假设第一个盒子放的i号球，则有两种情况
①恰好第i个盒子放的球就是一号球，则剩下的$n-2$个球继续错排，方案数为$D(n-2)$
②第i个盒子放的不是一号球，此时形成了一条新的限制：一号球不能放进i号盒
除去第一个盒子和i号球的剩下$n-1$个球和$n-1$个盒子，继续错排的方案数为$D(n-1)$