排列與組合

排列

排列的定義與基本性質

定義 設一個集合 \(S\) 中有 \(n\) 個元素，從中有序地取出 \(m(0\leq 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)!}\) ，其中 \(0\leq m \leq n\)。

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

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

性質1的證明：

考慮乘法原理，按順序選數，第 \(i(1\leq i\leq m)\) 個數有 \(n-i+1\) 種選法，乘在一起可得原式。

性質2的證明：

考慮乘法原理，第一個數有 \(n\) 種選法，再從剩下的 \(n-1\) 個數裡選 \(m-1\) 個有 \(\text{P}_{n-1}^{m-1}\) 種排列，所以 \(\text{P}_n^m = n\text{P}_{n-1}^{m-1}\) 。

性質3的證明：

考慮加法原理，考慮分兩類：

1. 先指定選一個元素，有 \(m\) 個位置可放，再從剩下 \(n-1\) 元素中選 \(m-1\) 個有 \(\text{P}_{n-1}^{m-1}\) 種排列。
2. 不選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\) 有遞推公式

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

性質3 \(D_n\) 有簡單表示式 \(D_n = \left\lfloor \dfrac{n!}{\text{e}} \right\rfloor\) 。

性質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(1\leq k\leq n-1)\) ，有兩種情況：

1. \(k\) 一定出現在位置 \(n\) ，那麼除去 \(k,n\) 剩下 \(n-2\) 個數錯排即可，共計 \(D_{n-2}\) 。
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_i\right| = \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)!\) ，對於 \(1\leq i_1 < i_2 < \cdots < i_k < n\) 共有 \(\dbinom{n}{k}\) 種方案，因此 \(\displaystyle \left| \bigcup_{i=1}^n S_i\right| = \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(0\leq 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 \leq +\infty(1\leq i\leq k)\) ，則 \(m\) 排列數為 \(k^m\) 。

性質1的證明：

不考慮元素重複的全排列為 \(n!\) ，再對每個元素的全排列 \(n_i!(1\leq i\leq 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(0\leq 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(0\leq i\leq 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(k\geq 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 \\ &= x\sum_{i=0}^k \binom{k}{i}x^{k-i}y^i + y\sum_{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(0\leq 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(1\leq 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(1\leq i \leq k)\) 個括號內選了 \(x_i\) 的方案數。

我們設多重集有 \(n_i(1\leq 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(0\leq 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(0\leq 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)(0\leq i \le k)\) ，則 \(\displaystyle \binom{n}{m} \equiv \prod_{i = 0}^k\binom{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 = \left\lfloor \dfrac{m}{p} \right\rfloor,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合併。

這個過程證明相當複雜，初學者可以學個板子略過了。

時間複雜度 \(O\left (\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\) 以內的質數，複雜度玄學，估計下面這個。

時間複雜度 \(O\left(n\log \dbinom{n}{m} \right)\)

空間複雜度 \(O\left( \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;
    }
}

多重集的組合

排列組合技巧

捆綁法

插空法

隔板法