Skip to main content

常用组合公式

排列​

Anm=n!(n−m)!， m≤nA_{n}^m= \frac{n!}{(n-m)!}，\ m\leq n

表示从 nn 个元素中，任意取出 mm 个，并按一定的顺序排列。

组合​

cnm=n!m!(n−m)!, m≤nc_{n}^m= \frac{n!}{m!(n-m)!},\ m\leq n

表示从 nn 个元素中任意取出 mm 个元素作为一组，没有顺序，因此需要多除以 m!m!.

性质：

  1. Cnm=Cnn−mC_{n}^m=C_{n}^{n-m}
  2. Cnm+Cnm−1=Cn+1mC_{n}^m+C_{n}^{m-1}=C_{n+1}^m，来源杨辉三角，例如从 nn 个男生和 11 个女生中任意选出 mm 个，则组合数应该是 Cn+1mC_{n+1}^m，也可以分开看，若选出的人中不包含女生：CnmC_{n}^m，包含女生：Cnm−1C_{n}^{m-1}
  3. mCnm=nCn−1m−1mC_{n}^m=nC_{n-1}^{m-1}，例如从 nn 个
  4. ∑i=0nCni=2n\sum_{i=0}^nC_{n}^i=2^n
  5. ∑i=0n(Cni)2=C2nn\sum_{i=0}^n(C_{n}^i)^2=C_{2n}^n

多项式展开定理​

(x1+x2+⋯+xt)n=∑n!n1!n2!⋯nt!x1n1⋯xtnt(x_{1}+x_{2}+\cdots+x_{t})^n=\sum \frac{n!}{n_{1}!n_{2}!\cdots n_{t!}}x_{1}^{n_{1}}\cdots x_{t}^{n_{t}}

其中 n1⋯ntn_{1}\cdots n_{t} 是满足 n1+n2+⋯+nt=nn_{1}+n_{2}+\cdots +n_t=n 的所有非负解，解的个数有 C(n+t−1,n)C(n+t-1,n)， 实际上是

C(n,n1)×C(n−n1,n2)×C(n−n1−n2,n3)×⋯×C(n−n1−⋯ ,nt)C(n,n_{1})\times C(n-n_{1},n_{2})\times C(n-n_{1}-n_{2}, n_{3})\times\cdots\times C(n-n_{1}-\cdots,n_{t})

化简的结果