avatar

组合数学习笔记

组合数学习笔记

定义:

排列:从 nn 个元素中选取 rr 个元素,当考虑顺序时,所有可能的方案一共有:

Anr=n!(nm)!A_n^r = \frac{n!}{(n - m)!}

组合:从 nn 个元素中选取 rr 个元素,当不计顺序时,所有可能的方案一共有:

Cnr=(nr)=n!m!(nm)!=AnmAmmC_n^r = \left ( n \\ r \right ) = \frac{n!}{m!(n - m)!} = \frac{A_n^m}{A_m^m}

组合数递推公式

如果将杨辉三角形写出来的话:

111121133114641\begin{array}{l} 1 \\ 1 & 1 \\ 1 & 2 & 1 \\ 1 & 3 & 3 & 1 \\ 1 & 4 & 6 & 4 & 1 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ \end{array}

会发现这个三角形中的第 (i,j)(i, j) 项恰好对应了组合数 CijC_i^j ,所以我们可以直观的得到这样一个式子:

Cnm=Cn1m1+Cn1mC_n^m = C_{n - 1}^{m - 1} + C_{n - 1}^m

一种证明方法是将组合数的式子带进去算,但这样证明太复杂了。

另一种证明方法:在 nn 个元素中选取 mm 个元素中,考虑元素 mm 有选与不选两种情况;当选 mm 时,则需要在剩下 n1n - 1 个元素中选取 m1m - 1 个元素,当不选 mm 时,则需要在剩下 n1n - 1 个元素中选取 mm 个元素。根据加法原理, Cnm=Cn1m1+Cn1mC_n^m = C_{n - 1}^{m - 1} + C_{n - 1}^m

  • 在后续证明中,将组合数的计算公式带入显然是一个万能的方法,但如果我们考虑好 CnmC_n^m 的意义,证明就会更容易些。

组合数及其相关性质

  • Cn+mn=Cn+mmC_{n+m}^n = C_{n + m}^m

显然 n+mn + m个物品中 选 nn 个元素的方案数等于挑出 mm 个元素不选的方案数。

  • Cnm=Cn1m1+Cn1mC_n^m = C_{n - 1}^{m - 1} + C_{n - 1}^m

  • Cn+r+1r=Cn+rr+Cn+r1r1++Cn0C_{n + r + 1}^r = C_{n + r}^r + C_{n + r - 1}^{r - 1} + \cdots + C_n ^ 0

反复套用上一个性质就可以证明。

  • CnlClr=CnrCnrlrC_n^lC_l^r = C_n^rC_{n - r}^{l - r}

对于 nn 个元素,先无序取出其中 ll 个元素,再无序从这 ll 个元素中取出其中 rr 个元素,与先无序取出 rr 个元素,再从剩余的 nrn-r 个元素中无序取出 lrl-r 个元素是等效的。

  • Cn0+Cn1+Cnn=2nC_n^0 + C_n^1 + \cdots C_n^n = 2^n

对于 nn 个互异元素,将其每种选择数相加,就是选取任意个元素的情况,对应到每个元素只有选和不选两种情况。

  • Cn0Cn1+Cn2=0C_n^0 - C_n^1 + C_n^2 - \cdots = 0

在杨辉三角中,第 nn 行每个排偶数位的元素相加等于第 n1n - 1 行元素每个元素相加,且每个排奇数位的元素相加也等于第 n1n - 1 行元素每个元素相加。

  • Crr+Cr+1r++Cnr=Cn+1r+1C_r^r + C_{r + 1}^r + \cdots + C_n^r = C_{n + 1}^{r + 1}

同样可以反复套用第二个性质。

  • (1+x)n=Σk=0nCnkxnk=Σk=0nCnkxk(1 + x)^n = \Sigma_{k = 0}^n C_n^kx^{n - k} = \Sigma_{k = 0}^n C_n^kx^k

二项式展开: (x+y)n=Σi=0nCnixniyi(x + y)^n = \Sigma_{i = 0}^nC_n^ix^{n - i}y^i ,证明可用数学归纳法

  • Σi=0nCni2=C2nn\Sigma_{i = 0}^n{C_n^i}^2 = C_{2n}^n

Σi=0nCni2=Σi=0nCni×Cnni\Sigma_{i = 0}^n{C_n^i}^2 = \Sigma_{i = 0}^nC_n^i \times C_n^{n - i} 即等于 C2nnC_{2n}^n

组合数取模

  • 目标:求出 Cnm?(modk)C_n^m \equiv ? \pmod k

情况一: k=1k = 1 太过于麻烦,跳过

情况二: k>1,nm107k > 1, nm \leq 10^7

使用组合数递推公式求并每步取模,时间复杂度 O(nm)O(nm)

情况三: n109,m104,k109n \leq 10^9, m \leq 10^4, k \leq 10^9

核心要点:将 CnmC_n^m 写为 n(n1)(nm+1)m!\frac{n(n - 1)\cdots(n - m + 1)}{m!} ,上下相除最多只用计算 O(m)O(m) 项。

对上下每一项进行质因数分解,然后统计每个质因子出现个数,快速幂合并。

情况四: n,m1010,kn, m \leq 10^10, k为小质数

Lucas 定理(下文将讲)。

情况五: n,m109,k105n,m \leq 10^9, k \leq 10^5

kk 质因数分解为 p1r1p2r2ptrtp_1^{r_1} \cdot p_2^{r_2} \cdots p_t^{r_t} ,计算每一个 CnmC_n^m % p_i^{r_i} ,最后用中国剩余定理合并。

Lucas 定理

对于求 CnmC_n^m % k 的值,一种方法是将 nnmm 分别变为 kk 进制的 tt 位数 n1,n2,,ntn_1, n_2, \cdots, n_tm1,m2,,mtm_1, m_2,\cdots, m_t ,位数不足的用前导零补足。 CnmC_n^m % k 就等于对这两个数的 kk 进制逐位求组合数相乘再取模。

CnmC_n^m % k = C_{n_1}^{m_1}\cdotC_{n_2}^{m_2} \cdots C_{n_t}^{m_t} % k

文章作者: Ender
文章链接: https://www.ender.xin/post/cd40da.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ender's blog
打赏
  • 微信和支付宝
    微信和支付宝

评论