组合数学笔记-排列与组合

技术分享 2年前 (2023-03-01) 0 999+

排列与组合

排列

排列的定义与基本性质

定义设一个集合 (S) 中有 (n) 个元素，从中有序地取出 (m(0leq m leq n)) 个元素排成一列，称为 (S) 的一个 (m) 排列。两个排列相同，当且仅当元素相同且顺序相同。我们记 (text{P}_n^m) 、 (text{A}_n^m) 或 (text{P}(n,m)) 表示 (S) 中 (m) 排列的总数。

约定当 (m>n) 时，(text{P}_n^m = 0) 。

全排列的定义 设一个集合 (S) 中有 (n) 个元素，其 (n) 排列称为全排列。

C++中，next_permutation 函数可以按字典序从小到大遍历数据的全排列，prev_permutation 函数与之相反。

性质1 (mathrm{P}_n^m = n(n-1)(n-2)cdots(n-m+1) = dfrac{n!}{(n-m)!}) ，其中 (0leq m leq n)。

性质2 (text{P}_n^m = ntext{P}_{n-1}^{m-1}) 。

性质3 (text{P}_n^m = m text{P}_{n-1}^{m-1} + text{P}_{n-1}^{m}) 。

性质1的证明：

考虑乘法原理，按顺序选数，第 (i(1leq ileq m)) 个数有 (n-i+1) 种选法，乘在一起可得原式。

性质2的证明：

考虑乘法原理，第一个数有 (n) 种选法，再从剩下的 (n-1) 个数里选 (m-1) 个有 (text{P}_{n-1}^{m-1}) 种排列，所以 (text{P}_n^m = ntext{P}_{n-1}^{m-1}) 。

性质3的证明：

考虑加法原理，考虑分两类：

先指定选一个元素，有 (m) 个位置可放，再从剩下 (n-1) 元素中选 (m-1) 个有 (text{P}_{n-1}^{m-1}) 种排列。

不选1指定的元素，从其他 (n-1) 元素里选 (m) 个，共 (text{P}_{n}^{m-1}) 种排列。

因此 (text{P}_n^m = m text{P}_{n-1}^{m-1} + text{P}_{n-1}^{m}) 。

错位排列

错位排列的定义与基本性质

定义设 (P=(p_1,p_2,cdots,p_n)) 是 (S={1,2,cdots,n}) 的一个排列，若对于任意的 (i in[1,n]) 满足 (p_i neq i) ，则称 (P) 是 (S) 的一个错位排列。我们记 (D_n) 表示 (S) 的错位排列的总数。

性质1 (D_n) 有递推公式

[D_n = begin{cases} 1 &, n = 0\ 0 &, n = 1\ 1 &, n = 2\ (n-1)(D_{n-1} + D_{n-2}) &, n geq 3 end{cases} ]

性质2 (D_n) 有通项公式 (displaystyle D_n = n!sum_{k=0}^n frac{(-1)^k}{k!}) 。

性质3 (D_n) 有简单表达式 (D_n = leftlfloor dfrac{n!}{text{e}} rightrfloor) 。

性质4 ({1,2,cdots ,n }) 的排列是错位排列的概率 (P_n) 有渐进 (lim_limits{n to infty} P_n = lim_limits{n to infty} dfrac{D_n}{n!} = dfrac{1}{text{e}}) ，表明 (D_n) 的增长率与 (n!) 仅相差常数倍。

性质1的证明：

考虑加法原理，设 (n) 出现在位置 (k(1leq kleq n-1)) ，有两种情况：

(k) 一定出现在位置 (n) ，那么除去 (k,n) 剩下 (n-2) 个数错排即可，共计 (D_{n-2}) 。

(k) 不能出现在位置 (n) ，那么可把位置 (n) 视作 (k) 的新位置与除了 (n) 的数进行错排，共计 (D_{n-1}) 。

因此再根据乘法原理，有 (D_n = (n-1)(D_{n-1}+D_{n-2})) 。

性质2的证明：

考虑减法原理，设全集 (U) 为 ([1,n]) 的全排列，则 (|U| = n!) ，设满足 (p_i neq i) 的排列的集合为 (S_i) ，那么满足 (p_i = i) 的集合为 (overline{S_i}) ，那么有 (displaystyle left| bigcap_{i=1}^n S_i right| = |U| - left| bigcup_{i=1}^n overline{S_i} right|) ，问题转换为求 (displaystyle left| bigcup_{i=1}^n overline{S_i} right|) 。

考虑容斥原理，有 (displaystyle left| bigcup_{i=1}^n S_iright| = sum_{k=1}^n (-1)^{k-1} sum_{1 leq i_1<i_2< cdots < i_k leq n} left| bigcap_{j=1}^k S_{i_j} right|) ，其中 (displaystyle left| bigcap_{j=1}^k S_{i_j} right|) 为所有 (i in T) 满足 (p_i = i) 的排列数，显然为 ((n-k)!) ，对于 (1leq i_1 < i_2 < cdots < i_k < n) 共有 (dbinom{n}{k}) 种方案，因此 (displaystyle left| bigcup_{i=1}^n S_iright| = sum_{k=1}^n (-1)^{k-1} binom{n}{k}(n-k)! = sum_{k=1}^n (-1)^{k-1} frac{n!}{k!}) 。

最后，错位排列数 (displaystyle left| bigcap_{i=1}^n S_i right| = |U| - left| bigcup_{i=1}^n overline{S_i} right| = n! - sum_{k=1}^n (-1)^{k-1} frac{n!}{k!} = n!sum_{k=0}^n frac{(-1)^k}{k!}) 。

圆排列

圆排列的定义与基本性质

定义设一个集合 (S) 中有 (n) 个元素，从中有序地取出 (m(0leq m leq n)) 个元素排成不分首尾围成一圈，称为 (S) 的一个 (m) 圆排列。两个圆排列相同，当且仅当元素相同且不分首位地顺序相同。我们记 (text{Q}_n^m) 表示 (S) 的 (m) 圆排列的总数。

性质1 (text{Q}_n^m = dfrac{text{P}_n^m}{m}) 。

性质1的证明：

对于每一种圆排列，我们可以规定首尾使其变成标准排列，共有 (m) 种首尾方案，因此有 (text{Q}_n^m cdot m = text{P}_n^m) ，所以 (text{Q}_n^m = dfrac{text{P}_n^m}{m}) 。

多重集排列

多重集排列的定义与基本性质

定义设多重集 (S = {n_1 cdot a_1,n_2 cdot a_2,cdots ,n_k cdot a_k}) ，从中任选 (m) 个元素组成排列，称为 (S) 的 (m) 排列。

多重组合数的定义 设多重集 (S = {n_1 cdot a_1,n_2 cdot a_2,cdots ,n_k cdot a_k}) ， (n = displaystyle sum_{i=1}^k n_i) ，则 (S) 的 (n) 排列（即全排列）的总数称为多重组合数，记为 (dbinom{n}{n_1,n_2,cdots ,n_k}) 。

性质1 设多重集 (S = {n_1 cdot a_1,n_2 cdot a_2,cdots ,n_k cdot a_k}) ，(n = displaystyle sum_{i=1}^k n_i) ，则全排列数为 (dbinom{n}{n_1,n_2,cdots ,n_k} = dfrac{n!}{displaystyle prod_{i=1}^k n_i!}) 。

性质2 设多重集 (S = {n_1 cdot a_1,n_2 cdot a_2,cdots ,n_k cdot a_k}) ，若 (m) 满足 (m leq n_i leq +infty(1leq ileq k)) ，则 (m) 排列数为 (k^m) 。

性质1的证明：

不考虑元素重复的全排列为 (n!) ，再对每个元素的全排列 (n_i!(1leq ileq k)) 去重，所以 (dbinom{n}{n_1,n_2,cdots ,n_k} = dfrac{n!}{displaystyle prod_{i=1}^k n_i!}) 。

性质2的证明：

因为选 (m) 个小于等于任意元素的个数，所以每次都能选 (k) 个元素，因此总数为 (k^m) 。

组合

组合的定义与基本性质

定义设一个集合 (S) 中有 (n) 个元素，从中无序地取出 (m(0leq m leq n)) 个元素组成集合，称为 (S) 的一个 (m) 组合。两个组合相同，当且仅当元素相同。我们记 (text{C}_n^m) 、 (dbinom{n}{m}) 或 (text{C}(n,m)) 表示 (S) 中 (m) 组合的总数。

约定当 (m>n) 时，(dbinom{n}{m} = 0) 。

性质1 (dbinom{n}{m} = dfrac{text{P}_n^m}{m!} = dfrac{n!}{m!(n-m)!}) 。

性质2 (dbinom{n}{m} = dbinom{n}{n-m}) 。

性质3 (dbinom{n}{m} = dfrac{n-m+1}{m} dbinom{n}{m-1}) 。

性质4 (dbinom{n}{m} = dfrac{n}{m} dbinom{n-1}{m-1}) 。

性质5（杨辉三角） (dbinom{n}{m} = dbinom{n-1}{m} + dbinom{n-1}{m-1}) 。

性质6 (displaystyle sum_{i=0}^n binom{i}{m} = binom{n+1}{m+1}) 。

性质7 (dbinom{n}{m} dbinom{m}{k} = dbinom{n}{k} dbinom{n-k}{m-k}) 。

性质8 (displaystyle sum_{i=0}^n binom{n-i}{i} = F_{n+1}) ，其中 (F) 是斐波那契数列。

性质1的证明：

先考虑顺序得到的总数为 (m) 排列数 (text{P}_n^m) ，而对于一种 (m) 组合有 (m!) 种排列方式，所以 (m!dbinom{n}{m} = text{P}_n^m) ，因此根据排列性质1可得 (dbinom{n}{m} = dfrac{text{P}_n^m}{m!} = dfrac{n!}{m!(n-m)!}) 。

性质2的证明：

方法1：

由性质1易得。

方法2：

(n) 个里选 (m) 个组合，等价于 (n) 个里选 (n-m) 不在组合。

性质5的证明：

方法1：

由性质1易得。

方法2：

画出杨辉三角，由数学归纳法易得。

方法3：

指定一个元素，如果一定不选它则有 (dbinom{n-1}{m}) 种组合，如果一定选它则有 (dbinom{n-1}{m-1}) 种组合，考虑加法原理，得证。

性质6的证明：

方法1：

根据性质5可得

[begin{aligned} sum_{i=0}^n binom{i}{m} &= sum_{i=m}^n binom{i}{m} \ &= binom{m+1}{m+1} + binom{m+1}{m} + binom{m+2}{m} +cdots + binom{n}{m} \ &= binom{m+2}{m+1} + binom{m+2}{m} + cdots + binom{n}{m} \ &= binom{m+3}{m+1} + cdots + binom{n}{m}\ &= binom{n+1}{m+1} end{aligned} ]

方法2：

从 ([0,n]) 的整数中选出 (m+1) 个数的组合数为 (dbinom{n+1}{m+1}) ，在这些组合中最大数为 (i(0leq ileq n)) 的组合数为 (dbinom{i}{m}) ，考虑加法原理得证。

性质7的证明：

方法1：

由性质1可得

[begin{aligned} binom{n}{m} binom{m}{k} &= frac{n!}{m!(n-m)!} cdot frac{m!}{k!(m-k)!} \ &= frac{n!}{k!} cdot frac{1}{(m-k)!(n-m)!} \ &= frac{n!}{k!(n-k)!} cdot frac{(n-k)!}{(m-k)!(n-m)!} \ &= binom{n}{k} binom{n-k}{m-k} \ end{aligned} ]

方法2：

左式是正着选，从 (n) 个元素中选 (m) 个，对于每个 (m) 组合再选 (k) 个的 (k) 组合的总数的总和。

右式是倒着选，先从 (n) 个元素中选 (k) 个，对于每个 (k) 组合从剩下 (n-k) 个元素中再选 (m-k) 个元素，代表这个 (k) 组合会被所有 (m) 组合选到的次数，最后总和与左式意义等价。

性质8的证明：

设 (G_n = displaystyle sum_{i=0}^n binom{n-i}{i}) ，则 (G_0 = 1 = F_1,G_1 = 1 = F_2) 。

假设当 (n = k+1(kgeq 0)) 时， (G_k = F_{k+1},G_{k+1} = F_{k+2}) 成立。

那么当 (n = k+2) 时，由性质5可得

[begin{aligned} G_{k}+G_{k+1} &= sum_{i = 0}^k binom{k-i}{i} + sum_{i = 0}^{k+1} binom{k+1-i}{i} \ &= sum_{i = 1}^{k+1} binom{k-i+1}{i-1} + sum_{i = 1}^{k+1} binom{k+1-i}{i} + 1 \ &= sum_{i = 1}^{k+1} left( binom{k+1-i}{i-1} + binom{k+1-i}{i} right) + 1 \ &= sum_{i = 1}^{k+1} binom{k+2-i}{i} + binom{k+2}{0} + binom{0}{k+2}\ &= sum_{i = 0}^{k+2} binom{k+2-i}{i} \ &= G_{k+2} end{aligned} ]

同时有 (G_{k}+G_{k+1} = F_{k+1}+F_{k+2} = F_{k+3}) ，因此 (G_{k+1} = F_{k+2},G_{k+2} = F_{k+3}) ，得证。

二项式定理

定理1（二项式定理） (displaystyle (x+y)^n = sum_{i=0}^n binom{n}{i}x^{n-i}y^i) 。

推论1（定理1的推论） (displaystyle sum_{i=0}^n dbinom{n}{i} = 2^n) 。
推论2（定理1的推论） (displaystyle sum_{i=0}^n (-1)^{i}dbinom{n}{i} = [n=0]) 。
推论3（推论2的推论） (displaystyle binom{n}{0} + binom{n}{2} + cdots = binom{n}{1} + binom{n}{3} + cdots = 2^{n-1}) ，其中 (n geq 1) 。

定理2（扩展二项式定理） (displaystyle left( sum_{i = 1}^k x_i right)^n = sum_{n_1+n_2+cdots + n_k = n} binom{n}{n_1,n_2,cdots ,n_k}prod_{i = 1}^k x_i^{n_i}) 。

广义组合数的定义 设 (alpha in R,m in N) ，则 (displaystyle binom{alpha}{m} = frac{displaystyle prod_{i = 0}^m(alpha-i)}{m!}) 。

定理3（广义二项式定理） (displaystyle (x+y)^alpha = sum_{i=0}^{infty} binom{alpha}{i}x^{alpha-i}y^i) ，其中 (alpha in R) 。

定理1的证明：

方法1：

当 (n = 0) 时显然得证。

假设当 (n = k) 时， (displaystyle (x+y)^k = sum_{i=0}^k binom{k}{i}x^{k-i}y^i) 成立。

当 (n = k+1) 时，根据组合基本性质5有

[begin{aligned} (x+y)^{k+1} &= (x+y)sum_{i=0}^k binom{k}{i}x^{k-i}y^i \ &= xsum_{i=0}^k binom{k}{i}x^{k-i}y^i + ysum_{i=0}^k binom{k}{i}x^{k-i}y^i \ &= sum_{i=0}^k binom{k}{i}x^{k+1-i}y^i + sum_{i=1}^{k+1} binom{k}{i-1}x^{k-i+1}y^i \ &= binom{k}{0}x^{k+1} + sum_{i=1}^k binom{k}{i}x^{k+1-i}y^i + sum_{i=1}^{k} binom{k}{i-1}x^{k-i+1}y^i + binom{k}{k}y^{k+1} \ &= binom{k}{0}x^{k+1} + sum_{i=1}^k binom{k+1}{i}x^{k+1-i}y^i + binom{k+1}{k+1}y^{k+1} \ &= sum_{i=0}^{k+1} binom{k+1}{i}x^{k+1-i}y^i \ end{aligned} ]

于是得证。

方法2：

我们枚举 (x,y) 的指数 (i,j) 满足 (i+j = n) 的情况，等价于枚举 (i(0leq i leq n)) 得到 (j = n - i) 。对于一个 (i) 的情况，需要求在 (n) 个 ((x+y)) 括号中有 (i) 个选 (x) 和 (n-i) 个选 (y) 的方案数。

我们可以 (n) 选 (i) 后 (n-i) 选 (n-i) 共 (dbinom{n}{i} dbinom{n-i}{n-i} = dbinom{n}{i}) 种方案。

当然，我们也可以理解为一个多重集的模型，有 (i) 个选 (x) 的 ((x+y)) 和 (n-i) 个选 (y) 的 ((x+y)) ，选择相同的 ((x+y)) 算相同的元素，不同的顺序算不同的方案，所以是求有限多重集的全排列数，为 (dbinom{n}{i,n-i} = dbinom{n}{i}) 种方案。

因此 (displaystyle (x+y)^n = sum_{i=0}^n binom{n}{i}x^{n-i}y^i) 。

定理2的证明：

同样可以使用归纳法，但比较复杂，我们使用定理1的证法2，即组合意义证明。

我们枚举 (x_i(1leq i leq k)) 的指数 (n_i) 满足 (n_1 + n_2 + cdots + n_k = n) 的情况。对于一组非负整数解 (n_1,n_2,cdots ,n_k) ，需要求在 (n) 个 ((x_1 + x_2 + cdots + x_k)) 括号中有 (n_i(1leq i leq k)) 个括号内选了 (x_i) 的方案数。

我们设多重集有 (n_i(1leq i leq k)) 个选 (x_i) 的 ((x_1+x_2+cdots + x_k)) ，其全排列数为 (dbinom{n}{n_1,n_2,cdots,n_k}) 。

因此 (displaystyle left( sum_{i = 1}^k x_i right)^n = sum_{n_1+n_2+cdots + n_k = n} binom{n}{n_1,n_2,cdots ,n_k}prod_{i = 1}^k x_i^{n_i}) 。

范德蒙德卷积

定理1（范德蒙德卷积） (displaystyle sum_{i = 0}^k dbinom{n}{i} dbinom{m}{k-i} = dbinom{n+m}{k}) 。

推论1（定理1的推论） (displaystyle sum_{i = -s}^r dbinom{n}{i+s} dbinom{m}{r-i} = dbinom{n+m}{s+r}) 。
推论2（定理1的推论） (displaystyle sum_{i = 0}^n dbinom{n}{i}dbinom{n}{i-1} = dbinom{2n}{n-1}) 。
推论3（定理1的推论） (displaystyle sum_{i = 0}^n dbinom{n}{i}^2 = dbinom{2n}{n}) 。
推论4（定理1的推论） (displaystyle sum_{i = 0}^m dbinom{n}{i} dbinom{m}{i} = dbinom{n+m}{m}) 。

定理1的证明：

方法1：

由二项式定理的定理1可得

[begin{aligned} sum_{k = 0}^{n+m} binom{n+m}{k} x^k &= (1+x)^{n+m} \ &= (1+x)^n(1+x)^m \ &= left( sum_{i = 0}^n binom{n}{i}x^i right)left( sum_{j = 0}^m binom{m}{j}x^j right) \ &= sum_{i = 0}^n sum_{j = 0}^m binom{n}{i} binom{m}{j} x^{i+j} \ &= sum_{k = 0}^{n+m} sum_{i = 0}^k binom{n}{i} binom{m}{k-i} x^k end{aligned} ]

根据待定系数法 (x^k) 的系数相同，可得 (displaystyle sum_{i = 0}^k dbinom{n}{i} dbinom{m}{k-i} = dbinom{n+m}{k}) 。

方法2：

一个集合有 (n+m) 个元素，从中选 (k) 个元素的方案数为 (dbinom{n+m}{k}) 。

其等价于，将集合分成 (n,m) 两部分，从 (n) 中选 (i(0 leq i leq k)) 个再从 (m) 中选 (k-i) 个，共 (displaystyle sum_{i = 0}^k dbinom{n}{i} dbinom{m}{k-i}) 种方案。

推论1的证明：

由定理1简单变换可得

[begin{aligned} sum_{i = 0}^k binom{n}{i} binom{m}{k-i} &= sum_{i=-r}^{k-r} binom{n}{i+r} binom{m}{k-i-r}\ &= sum_{i=-r}^{s} binom{n}{i+r} binom{m}{s-i} \ &= binom{n+m}{s+r} end{aligned} ]

于是得证。

推论2的证明：

由定理1简单变换可得

[begin{aligned} sum_{i = 0}^n binom{n}{i}binom{n}{i-1} &= sum_{i = 0}^n binom{n}{i}binom{n}{n-i+1}\ &= binom{2n}{n+1} \ &= binom{2n}{n-1} end{aligned} ]

于是得证。

推论3的证明：

由定理1简单变换可得

[begin{aligned} sum_{i = 0}^n binom{n}{i}^2 &= sum_{i = 0}^n binom{n}{i}binom{n}{n-i}\ &= binom{2n}{n} \ end{aligned} ]

于是得证。

推论4的证明：

方法1：

由定理1简单变换可得

[begin{aligned} sum_{i = 0}^n binom{n}{i}binom{m}{i} &= sum_{i = 0}^n binom{n}{i}binom{m}{m-i}\ &= binom{n+m}{m} \ end{aligned} ]

于是得证。

方法2：

在 (n times m) 的网格图上，从 ((0,0)) 走到 ((n,m)) ，只能向右或者向下走，有多少方案。

显然会向右走 (m) 步和向下走 (n) 步共 (n+m) 步，所以方案数是 (dbinom{n+m}{m} dbinom{n}{n} = dbinom{n+m}{m}) 。

其等价于，将 (n+m) 步分为 (n,m) 步，在 (n) 步中选 (i(0leq i leq m)) 步向右，然后在 (m) 步选 (m-i) 步向右，有 (displaystyle sum_{i = 0}^m dbinom{n}{i} dbinom{m}{i}) 种方案。

卢卡斯定理

定理1（卢卡斯定理） 若 (p) 是质数，则 (dbinom{n}{m} equiv dbinom{n bmod p}{m bmod p} dbinom{lfloor n/p rfloor}{lfloor m/p rfloor} pmod p) 。

推论1（定理1的推论） 若 (p) 是质数，整数 (n,m(0leq m leq n)) 的 (p) 进制表达分别为 (n = a_ka_{k-1}cdots a_0, m = b_kb_{k-1}cdots b_0) ，其中 (a_i,b_i in[0,p)(0leq i le k)) ，则 (displaystyle binom{n}{m} equiv prod_{i = 0}^kbinom{a_i}{b_i}pmod p) 。

定理1的证明：

先证明 ((x+y)^p equiv x^p + y^p pmod p) ，其中 (p) 为素数。

考虑二项式 ((x+y)^p) ，根据二项式定理有 (displaystyle (x+y)^p = sum_{i=0}^p binom{p}{i}x^{p-i}y^i) ，其中 (dbinom{p}{i} = dfrac{p!}{i!(p-i)!}) ，显然当且仅当 (i = 0) 或 (i = p) 时 (dbinom{p}{i}) 没有质因子 (p) 且此时值为 (1) ，因此 (dbinom{p}{i} equiv [i = 0 or i = p] pmod p) ，所以 ((x+y)^p equiv x^p + y^p pmod p) 。

现在我们证明定理。

考虑二项式 ((1+x)^n) ，我们有

[begin{aligned} (1+x)^n &equiv (1+x)^{p lfloor n/p rfloor} (1+x)^{n , bmod , p} \ &equiv (1+x^p)^{lfloor n/p rfloor}(1+x)^{n , bmod , p} \ &equiv left( sum_{i=0}^{lfloor n/p rfloor} binom{lfloor n/p rfloor}{i}x^{ip} right) left( sum_{j=0}^{n , bmod , p} binom{n bmod p}{j}x^j right) \ &equiv sum_{i=0}^{lfloor n/p rfloor} sum_{j=0}^{n , bmod , p} binom{lfloor n/p rfloor}{i} binom{n bmod p}{j} x^{ip+j} pmod p end{aligned} ]

其中 (j in [0,n bmod p],n bmod p<p) ，那么不会有同一组 ((i,j)) 使得 (ip+j) 相等，因此和式里的系数就是 (x^{ip+j}) 的系数。

根据二项式定理 (displaystyle (1+x)^n = sum_{i=0}^n dbinom{n}{i}x^i) ， (x^m) 的系数为 (dbinom{n}{m}) 。在模 (p) 下，令 (ip + j = m) 有 (i = leftlfloor dfrac{m}{p} rightrfloor,j = m bmod p) ， (x^m) 的系数为 (dbinom{n bmod p}{m bmod p} dbinom{lfloor n/p rfloor}{lfloor m/p rfloor}) 。因此，根据待定系数法可得， (dbinom{n}{m} equiv dbinom{n bmod p}{m bmod p} dbinom{lfloor n/p rfloor}{lfloor m/p rfloor} pmod p) 。

推论1的证明：

把定理1的 (n,m) 持续递推，发现每次得到的都是 (p) 进制下的数位，因此得证。

组合数的求法

加法递推

根据性质5可得加法递推公式 (dbinom{n}{m} = dbinom{n-1}{m} + dbinom{n-1}{m-1}) ，依次递推可得 (0 leq m leq n) 的所有组合数。

这个递推在模数为素数时，完全可以被公式法替代，其他情况可以考虑使用。

时间复杂度 (O(n^2))

空间复杂度 (O(n^2))

const int P = 1e9 + 7; namespace CNM {     const int N = 2e3 + 7;     int c[N][N];     void init(int n) {         for (int i = 0;i <= n;i++)             for (int j = 0;j <= i;j++)                 c[i][j] = 0 < j && j < i ? (c[i - 1][j - 1] + c[i - 1][j]) % P : 1;     }     int C(int n, int m) {         if (n == m && m == -1) return 1; //* 隔板法特判         if (n < m || m < 0) return 0;         return c[n][m];     } }

乘法递推

根据性质3可得乘法递推公式 (dbinom{n}{m} = dfrac{n-m+1}{m} dbinom{n}{m-1}) ，可以直接求确定 (n) 的组合数，注意先乘法后除法。

可以利用性质2 (dbinom{n}{m} = dbinom{n}{n-m}) 去掉一半计算量。

当我们无法保存加法递推的所有组合数，但只需要一行组合数时，可以考虑此法。

注意此法不可直接取模，并且取模情况可以由公式法直接替代。

时间复杂度 (O(n))

空间复杂度 (O(n))

namespace CNM {     const int N = 34;     int n, Cn[N];     void init(int _n) {         n = _n;         Cn[0] = Cn[n] = 1;         for (int i = 1;2 * i <= n;i++) Cn[i] = Cn[n - i] = 1LL * (n - i + 1) * Cn[i - 1] / i;     }     int C(int m) {         if (n < m || m < 0) return 0;         return Cn[m];     } }

公式法

公式法是组合数取素数模时最好的解法，其利用逆元处理除法求 (dbinom{n}{m} = dfrac{n!}{m!(n-m)!}) ，可以在线性时间内处理出 (0 leq m leq n) 的所有组合数。

公式法在复杂度上优于加法递推，与乘法递推相同；在使用范围上与加法递推相同，优于乘法递推，可以完全替代前两个方法。

时间复杂度 (O(n))

空间复杂度 (O(n))

const int P = 1e9 + 7; namespace Number_Theory {     const int N = 1e7 + 7;     int qpow(int a, ll k) {         int ans = 1;         while (k) {             if (k & 1) ans = 1LL * ans * a % P;             k >>= 1;             a = 1LL * a * a % P;         }         return ans;     }     int fact[N], invfact[N];     void init(int n) {         fact[0] = 1;         for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;         invfact[n] = qpow(fact[n], P - 2);         for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;     } } namespace CNM {     using namespace Number_Theory;     int C(int n, int m) {         if (n == m && m == -1) return 1; //* 隔板法特判         if (n < m || m < 0) return 0;         return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;     } }

卢卡斯定理

在模数为不大的素数，但 (n) 很大时，可以考虑用卢卡斯定理 (dbinom{n}{m} equiv dbinom{n bmod p}{m bmod p} dbinom{lfloor n/p rfloor}{lfloor m/p rfloor} pmod p) 分解组合数，再利用公式法求解。

时间复杂度 (O(p+ log n))

空间复杂度 (O(n))

const int P = 1e5 + 3; namespace Number_Theory {     const int N = 1e5 + 7;     int qpow(int a, ll k) {         int ans = 1;         while (k) {             if (k & 1) ans = 1LL * ans * a % P;             k >>= 1;             a = 1LL * a * a % P;         }         return ans;     }     int fact[N], invfact[N];     void init(int n) {         fact[0] = 1;         for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;         invfact[n] = qpow(fact[n], P - 2);         for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;     } } namespace CNM {     using namespace Number_Theory;     int C(int n, int m) {         if (n == m && m == -1) return 1; //* 隔板法特判         if (n < m || m < 0) return 0;         return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;     } } namespace Lucas {     int C(int n, int m) {         int ans = 1;         while (n) {             ans = 1LL * ans * CNM::C(n % P, m % P) % P;             n /= P, m /= P;         }         return ans;     } }

扩展卢卡斯定理

扩展卢卡斯定理解决了卢卡斯定理无法解决的非素数模数情况，其主要利用了CRT将问题分解，又通过威尔逊定理相关解决了质数幂模数的组合数求模问题。

证明：

我们先将问题分解为多个质数幂的模，因为模数互质，所以最后可以用CRT合并，于是有

[left{ begin{aligned} binom{n}{m} &equiv a_1 pmod {p_1^{alpha_1}}\ binom{n}{m} &equiv a_2 pmod {p_2^{alpha_2}}\ &vdots \ binom{n}{m} &equiv a_k pmod {p_k^{alpha_k}}\ end{aligned} right. ]

接下来我们要求出 (k) 个方程中的 (a_i) 。

不妨我们考虑其中一个方程 (dbinom{n}{m} equiv dfrac{n!}{m!(n-m)!}equiv a pmod {p^{alpha}}) ，我们可以对各个阶乘取模后合并，其中分母取逆元。

注意到阶乘可能含有因子 (p) ，可能导致结果为 (0) 或者无法求逆元，但实际上在分式中因子 (p) 会被消除，因此我们可以考虑先将 (p) 因子全部提出，再对除去所有 (p) 因子的阶乘求模，于是有 (dfrac{dfrac{n!}{v_p(n!)}}{dfrac{m!}{v_p(m!)} cdot dfrac{(n-m)!}{v_p((n-m)!)}}cdot p^{x-y-z} equiv a pmod{p^alpha}) 。

不妨考虑 (dfrac{n!}{v_p(n!)}) 的求法，根据威尔逊定理的推论1有 (dfrac{n!}{v_p(n!)} equiv (pm 1)^{lfloor n/p^alpha rfloor} dfrac{lfloor n/p rfloor!}{v_p(lfloor n/p rfloor!)} ((n bmod p^alpha)!)_p pmod{p^alpha}) ，其中 (pm 1) 的判定根据威尔逊定理的定理5即可， (((n bmod p^alpha)!)_p) 可以预处理，于是我们可以递归求解。但这是尾递归，我们可以改为迭代形式。因此，我们将分式三部分的余数求完，对分母取逆元变为乘法， (p^{x-y-z}) 利用快速幂求解，最后相乘即可求出 (a) 。

最后，求完 (k) 个方程的余数后，我们通过CRT合并。

这个过程证明相当复杂，初学者可以学个板子略过了。

时间复杂度 (Oleft (displaystyle sum_{i}(log_{p_i}n + log p_i + p_i^{alpha_i}) right))

空间复杂度 (O(max{p_i^{alpha_i}}))

namespace Number_Theory {     ll exgcd(ll a, ll b, ll &x, ll &y) {         if (!b) { x = 1, y = 0; return a; }         ll d = exgcd(b, a % b, x, y);         x -= (a / b) * y, swap(x, y);         return d;     }     ll inv(ll a, ll P) {         ll x, y;         exgcd(a, P, x, y);         return (x % P + P) % P;     }     int qpow(int a, ll k, int P) {         int ans = 1;         while (k) {             if (k & 1) ans = 1LL * ans * a % P;             k >>= 1;             a = 1LL * a * a % P;         }         return ans;     } } namespace CRT {     using namespace Number_Theory;     ll solve(int k, const vector<int> &a, const vector<int> &p) {         ll P = 1, ans = 0;         for (int i = 1;i <= k;i++) P *= p[i];         for (int i = 1;i <= k;i++) {             ll Pi = P / p[i], invPi = inv(Pi, p[i]);             (ans += (__int128_t)a[i] * Pi * invPi % P) %= P;         }         return ans;     } } namespace exLucas {     using namespace Number_Theory;     int fpr(ll n, int p, int P) {         vector<int> f(P);         f[0] = 1;         for (int i = 1;i < P;i++)             f[i] = 1LL * f[i - 1] * (i % p ? i : 1) % P;         int ans = 1;         while (n) {             if ((p != 2 || P <= 4) && ((n / P) & 1)) ans = P - ans;             ans = 1LL * ans * f[n % P] % P;             n /= p;         }         return ans;     }     int Cpr(ll n, ll m, int p, int P) {         int cnt = 0;         for (ll i = n;i;i /= p) cnt += i / p;         for (ll i = m;i;i /= p) cnt -= i / p;         for (ll i = n - m;i;i /= p) cnt -= i / p;         return 1LL * qpow(p, cnt, P) * fpr(n, p, P) % P *             inv(fpr(m, p, P), P) % P * inv(fpr(n - m, p, P), P) % P;     }     int C(ll n, ll m, int P) {         if (n == m && m == -1) return 1; //* 隔板法特判         if (n < m || m < 0) return 0;         int k = 0;         vector<int> a(20), p(20);         for (int i = 2;i * i <= P;i++) {             if (!(P % i)) {                 p[++k] = 1;                 while (!(P % i)) p[k] *= i, P /= i;                 a[k] = Cpr(n, m, i, p[k]);             }         }         if (P > 1) p[++k] = P, a[k] = Cpr(n, m, P, p[k]);         return CRT::solve(k, a, p);     } }

枚举质因子重数

对于不取模的大组合数，直接使用高精度乘除法的复杂度比较大，因此考虑先求出质因子的幂次，再高精度累乘即可。

注意先预处理 (n) 以内的质数，复杂度玄学，估计下面这个。

时间复杂度 (Oleft(nlog dbinom{n}{m} right))

空间复杂度 (Oleft( log dbinom{n}{m} right))

///继承vector解决位数限制(当前最大位数是9倍整型最大值)，操作方便（注意size()返回无符号长整型，尽量不要直接把size放入表达式） struct Huge_Int:vector<long long> {      static const int WIDTH = 9;///压位数，压9位以下 比较安全     static const long long BASE = 1e9;///单位基     static const long long MAX_INT = ~(1 << 31);///最大整型     bool SIGN;      ///初始化，同时也可以将低精度转高精度、字符串转高精度     ///无需单独写高精度数和低精度数的运算函数，十分方便     Huge_Int(long long n = 0) { *this = n; }     Huge_Int(const string &str) { *this = str; }      ///格式化，包括进位和去前导0，用的地方很多，先写一个     Huge_Int &format(int fixlen = 1) {//去0后长度必须大于等于fixlen，给乘法用的         while (size() > fixlen && !back()) pop_back();//去除最高位可能存在的0         if (!back()) SIGN = 0;         for (int i = 1; i < size(); ++i) {             (*this)[i] += (*this)[i - 1] / BASE;             (*this)[i - 1] %= BASE;         }//位内进位         while (back() >= BASE) {             push_back(back() / BASE);             (*this)[size() - 2] %= BASE;         }//位外进位         return *this;//为使用方便，将进位后的自身返回引用     }      ///归零     void reset() {         clear();         SIGN = 0;     }      ///重载等于，初始化、赋值、输入都用得到     Huge_Int operator=(long long n) {         reset();         SIGN = n < 0;         if (SIGN) n = -n;         push_back(n);         format();         return *this;     }     Huge_Int operator=(const string &str) {         reset();         if (str.empty()) push_back(0);         SIGN = str[0] == '-';         for (int i = str.length() - 1;i >= 0 + SIGN;i -= WIDTH) {             long long tmp = 0;             for (int j = max(i - WIDTH + 1, 0 + SIGN);j <= i;j++)                 tmp = (tmp << 3) + (tmp << 1) + (str[j] ^ 48);             push_back(tmp);         }         format();         return *this;     }      ///重载输入输出     friend istream &operator>>(istream &is, Huge_Int &tmp) {         string str;         if (!(is >> str)) return is;         tmp = str;         return is;     }     friend ostream &operator<<(ostream &os, const Huge_Int &tmp) {         if (tmp.empty()) os << 0;         else {             if (tmp.SIGN) os << '-';             os << tmp[tmp.size() - 1];         }         for (int i = tmp.size() - 2;i >= 0;i--) {             os << setfill('0') << setw(WIDTH) << tmp[i];         }         return os;     }      ///重载逻辑运算符，只需要小于，其他的直接代入即可     ///常量引用当参数，避免拷贝更高效     friend bool operator<(const Huge_Int &a, const Huge_Int &b) {         if (a.SIGN ^ b.SIGN) return a.SIGN;         if (a.size() != b.size()) return a.SIGN ? a.size() > b.size():a.size() < b.size();         for (int i = a.size() - 1; i >= 0; i--)             if (a[i] != b[i])return a.SIGN ? a[i] > b[i] : a[i] < b[i];         return 0;     }     friend bool operator>(const Huge_Int &a, const Huge_Int &b) { return b < a; }     friend bool operator>=(const Huge_Int &a, const Huge_Int &b) { return !(a < b); }     friend bool operator<=(const Huge_Int &a, const Huge_Int &b) { return !(a > b); }     friend bool operator!=(const Huge_Int &a, const Huge_Int &b) { return a < b || b < a; }     friend bool operator==(const Huge_Int &a, const Huge_Int &b) { return !(a != b); }      ///重载负号     friend Huge_Int operator-(Huge_Int a) { return a.SIGN = !a.SIGN, a; }      ///绝对值函数     friend Huge_Int abs(Huge_Int a) { return a.SIGN ? (-a) : a; }      ///加法，先实现+=，这样更简洁高效     friend Huge_Int &operator+=(Huge_Int &a, const Huge_Int &b) {         if (a.SIGN ^ b.SIGN) return a -= (-b);         if (a.size() < b.size()) a.resize(b.size());         for (int i = 0; i < b.size(); i++) a[i] += b[i];//被加数要最大位，并且相加时不要用未定义区间相加         return a.format();     }     friend Huge_Int operator+(Huge_Int a, const Huge_Int &b) { return a += b; }     friend Huge_Int &operator++(Huge_Int &a) { return a += 1; }     friend Huge_Int operator++(Huge_Int &a, int) {         Huge_Int old = a;         ++a;         return old;     }      ///减法，由于后面有交换，故参数不用引用     friend Huge_Int &operator-=(Huge_Int &a, Huge_Int b) {         if (a.SIGN ^ b.SIGN) return a += (-b);         if (abs(a) < abs(b)) {             Huge_Int t = a;             a = b;             b = t;             a.SIGN = !a.SIGN;         }         for (int i = 0; i < b.size(); a[i] -= b[i], i++) {             if (a[i] < b[i]) {//需要借位                 int j = i + 1;                 while (!a[j]) j++;                 while (j > i) a[j--]--, a[j] += BASE;             }         }         return a.format();     }     friend Huge_Int operator-(Huge_Int a, const Huge_Int &b) { return a -= b; }     friend Huge_Int &operator--(Huge_Int &a) { return a -= 1; }     friend Huge_Int operator--(Huge_Int &a, int) {         Huge_Int old = a;         --a;         return old;     }       ///乘法，不能先实现*=，因为是类多项式相乘，每位都需要保留，不能覆盖     friend Huge_Int operator*(const Huge_Int &a, const Huge_Int &b) {         Huge_Int n;         n.SIGN = a.SIGN ^ b.SIGN;         n.assign(a.size() + b.size() - 1, 0);//表示乘积后最少的位数(可能会被format消掉，因此添加了format参数)         for (int i = 0; i < a.size(); i++) {             for (int j = 0; j < b.size(); j++)                 n[i + j] += a[i] * b[j];             n.format(n.size());//提前进位         }         return n;//最后进位可能会溢出     }     friend Huge_Int &operator*=(Huge_Int &a, const Huge_Int &b) { return a = a * b; }      ///带余除法函数，方便除法和模运算，暂时写不出高效的高精与高精的除法     friend Huge_Int divmod(Huge_Int &a, const Huge_Int &b) {//O(logn)，待修改         assert(b != 0);         Huge_Int n;         if (-MAX_INT - 1 <= b && b <= MAX_INT) {//除数小于等于整型才能用这个，不然会溢出             n = a;             n.SIGN = a.SIGN ^ b.SIGN;             long long rest = 0;             long long bl = 0;             for (int i = b.size() - 1;i >= 0;i--) bl = bl * BASE + b[i];             for (int i = n.size() - 1;i >= 0;i--) {                 rest *= BASE;                 n[i] += rest;                 rest = n[i] % bl;                 n[i] /= bl;             }             a = a.SIGN ? (-rest) : rest;             return n.format();         }         else {//考虑倍增或者二分优化             n.SIGN = a.SIGN ^ b.SIGN;             for (int i = a.size() - b.size(); abs(a) >= abs(b); i--) {//减法代替除法                 Huge_Int c, d;                 d.assign(i + 1, 0);                 d.back() = 1;                 d.SIGN = n.SIGN;                 c = b * d;//提高除数位数进行减法                 while (abs(a) >= abs(c)) a -= c, n += d;                 d.pop_back();                 if (!d.empty()) {//遍历压的位                     d.back() = BASE / 10;                     for (int i = 1;i < WIDTH;i++) {                         c = b * d;                         while (abs(a) >= abs(c)) a -= c, n += d;                         d.back() /= 10;                     }                 }             }             return n;         }     }     friend Huge_Int operator/(Huge_Int a, const Huge_Int &b) { return divmod(a, b); }     friend Huge_Int &operator/=(Huge_Int &a, const Huge_Int &b) { return a = a / b; }     friend Huge_Int &operator%=(Huge_Int &a, const Huge_Int &b) { return divmod(a, b), a; }     friend Huge_Int operator%(Huge_Int a, const Huge_Int &b) { return a %= b; } };  namespace Number_Theory {     const int N = 1e6 + 7;     bool vis[N];     vector<int> prime;     void get_prime(int n) {         for (int i = 2;i <= n;i++) {             if (!vis[i]) prime.push_back(i);             for (auto j : prime) {                 if (i * j > n) break;                 vis[i * j] = 1;                 if (!(i % j)) break;             }         }     } } namespace Legendre {     using namespace Number_Theory;     int fact_pexp(int n, int p) {         int cnt = 0;         while (n) {             cnt += n / p;             n /= p;         }         return cnt;     } } namespace CNM {     using namespace Number_Theory;     Huge_Int C(int n, int m) {         if (n == m && m == -1) return 1; //* 隔板法特判         if (n < m || m < 0) return 0;         Huge_Int ans(1);         for (int i = 0;i < prime.size();i++) {             int k =                 Legendre::fact_pexp(n, prime[i]) -                 Legendre::fact_pexp(m, prime[i]) -                 Legendre::fact_pexp(n - m, prime[i]);             int p = prime[i];             while (k) {                 if (k & 1) ans *= p;                 k >>= 1;                 p *= p;             }         }         return ans;     } }

多重集组合

多重集组合的定义与基本性质

定义设多重集 (S = {n_1 cdot a_1,n_2 cdot a_2,cdots ,n_k cdot a_k}) ，从中任选 (m) 个元素组成集合，称为 (S) 的 (m) 组合。

性质1 设多重集 (S = {n_1 cdot a_1,n_2 cdot a_2,cdots ,n_k cdot a_k}) ，若 (m) 满足 (m leq n_i leq +infty(1leq ileq k)) ，则 (m) 组合数为 (dbinom{k+m-1}{m}) 。

性质1的证明：

可以先将 (m) 个物品排成一排，然后指定物品的是哪种物品。因为是无序的，我们只需要考虑每种元素有几个即可，因此可以按顺序划分 (k) 个组别，一个组代表一个种类，同组的元素是同种的。我们用 (k-1) 个隔板划分 (k) 个组，如果把隔板也当成一个位置，那么物品和隔板一共 (m+k-1) 个位置，我们从中选 (m) 个位置放物品，其他放隔板即可，共 (dbinom{k+m-1}{m}) 种方案。这就是隔板法的一种应用。

该问题等价于 (x_1+x_2+cdots+x_k = n) 的非负整数解个数，我们有 (k) 种 (1) ，第 (i) 种代表在 (x_i) 的 (1) 。每种 (1) 都是无限的，这对应着 (x_i) 的范围是 ([0,+infty)) 。

计数技巧

计数的方法与原则

方法将目标方案合理分解为多个简单部分或步骤，利用计数原理合并。

原则分解的方案应该不重不漏覆盖原方案，即新方案与原方案产生一一映射的关系。

捆绑法

描述当要求某些元素相邻时，我们可以把它们先看作一个整体与其他元素计数，再对这个整体内部计数，用乘法原理合并。

应用有 (1,2,3,4,5) 五个人，其中 (1,2) 和 (3,4) 分别相邻，求排列数。我们把 (1,2) 和 (3,4) 分别捆绑在一起，先对 ((1,2),(3,4),5) 排列，共 (text{P}_3^3) 种，再分别对两个整体内部排列，分别为 (text{P}_2^2,text{P}_2^2) 种，因此共计 (text{P}_3^3text{P}_2^2text{P}_2^2) 种排列。

插空法

描述当要求某些元素两两不相邻时，我们可以先把其他元素放好，再把要求不相邻的元素插入不同的空隙或两端。

应用有 (1,2,3,4,5,6,7) 七个人，其中 (1,2,3) 两两不相邻，求排列数。我们先把 (4,5,6,7) 先排好，共 (text{P}_4^4) 种，再将 (1,2,3) 插入其中，有 (5) 个可插入位置，共 (text{P}_5^3) 种，因此共计 (text{P}_4^4 text{P}_5^3) 种排列。