组合数学习笔记

定义:

排列:从 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

扩展 Lucas 定理(下文也将讲)。

Lucas 定理

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

CnmCn1m1Cn2m2Cntmt(modk)C_n^m \equiv C_{n_1}^{m_1} \cdot C_{n_2}^{m_2} \cdots C_{n_t}^{m_t} \pmod k

扩展 Lucas 定理

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

如何求 Cnm mod pkC_n^m\ mod\ p^k 呢?

先将 CnmC_n^m 写为 n!m!(nm)!\frac{n!}{m!(n - m)!} ,则可以将这里面每个阶乘都写为 przp^r \cdot z 的形式,原式的值就很好求了。

对于质数 pp ,有 n!=przn! = p^r \cdot z ,所以可以把这 prp^r 个数写出来,将每个 prp^r 的因子都提出来,剩下的数得到一个新的序列:

fac=1,2,,p1,1,p+1,p+2,,2p1,2,2p+1,2p+2,,pr1,1fac = 1, 2, \cdots , p - 1, 1, p + 1, p + 2 , \cdots , 2p - 1, 2, 2p + 1, 2p + 2 , \cdots , p^r - 1 , 1

同时还可以记录当前数贡献了几个 prp^r 的因子,对应上序列为:

num=0,0,,0,1,0,0,,0,1,0,0,,0,rnum = 0, 0, \cdots , 0, 1, 0, 0, \cdots , 0, 1, 0, 0, \cdots, 0, r

则显然 i!=fac[i]pnum[i]i! = fac[i] \cdot p^{num[i]} ,若 nprn \leq p^r ,则 n!n! 可以直接查表求出。

n>prn > p^r 时,将 pr+1,pr+2,,2prp^r + 1, p^r + 2, \cdots, 2p^rprp^r 的因子提出来可以得到以下序列:

1,2,,p1,1,p+1,p+2,,2p1,2,2p+1,2p+2,,pr1,21, 2, \cdots , p - 1, 1, p + 1, p + 2 , \cdots , 2p - 1, 2, 2p + 1, 2p + 2 , \cdots , p^r - 1 , 2

观察这个序列可以发现这个序列与序列 facfac 只差最后一个数,所以对于 (i1)pr+1(i - 1) \cdot p^r + 1ipri \cdot p^r 这个序列提出 prp^r 的因子后 ,最后一个数显然等于 ii

如果只观察所有段序列的最后一个数,显然还需要计算 npr!\lfloor \frac{n}{p^r} \rfloor ! ,这就回到了之前的问题,所以可以通过递归的形式求解 n!n!

所以我们可以通过这种方法求出 n!,m!,(nm)!n!, m!, (n - m)! 的值分别为 x1py1,x2py2,x3py3x_1 \cdot p^{y_1}, x_2 \cdot p^{y_2}, x_3 \cdot p^{y_3} ,则:

Cnm mod pr=x1x2x3py1y2y3 mod prC_n^m\ mod\ p^r= \frac{x_1}{x_2 \cdot x_3} \cdot p^{y_1 - y_2 - y_3} \ mod\ p^r