組合數學基礎
組合數學非常有用！我們先從一點點簡單的性質開始
簡單原理
-
加法原理
這非常簡單，我們舉一個例子即可：考慮我有 \(5\) 個紅蘋果和 \(3\) 個綠蘋果，如果你要選一個蘋果去吃，那么你一共有 \(5 + 3 = 8\) 種選擇的方法
-
乘法原理
同樣非常簡單：考慮我有 \(5\) 個蘋果，涵兒有 \(6\) 個蘋果，我們各自拿出一個蘋果，那么一共有 \(5 \times 6 = 30\) 種拿出的方案
-
減法原理和除法原理
本質與加法原理和乘法原理相似，這里不做展開
-
抽屜原理
(廣義）如果 \(n\) 個物品一共有 \(k\) 種狀態，那么至少有 \(\lceil \frac nk \rceil\) 種物品處于一個狀態
推論：一個從有 \(> k\) 個元素的集合映射到 \(k\) 個元素的集合的函數一定不是一對一函數。
終于正式開始將排列組合了！
排列
定理：具有 \(n\) 個元素的集合，選出 \(r\) 個排列的可能數（順序相關）
\[P(n, r) = n(n - 1)(n - 2)\cdots(n - r + 1) \]
證明：由于順序相關，不能選擇同一個數多次，那么第一個位置有 \(n\) 種選法，第二個位置有 \(n - 1\) 中選法，以此類推，第 \(i\) 個位置有 \(n - i + 1\) 種選法?？紤]乘法原理，那么就得出了上述結論。
特殊的：只要 \(n\) 是一個非負整數，那么 \(P(n, 0) = 1\)，因為恰好有一種方法來排列 \(0\) 個元素
簡寫公式：一般來說，我們不會寫成上述形式，而是
\[P(n, r) = \frac {n!}{(n - r)!} \]
多重排列
考慮這樣一個問題：我有 \(7\) 個盤子，\(2\) 個蘋果，\(3\) 個橘子和 \(2\) 個桃子，分別在一個盤子中放一個水果，一共有多少種放法（我們認為同一種水果是相同的）？
經過計算，一共有 \(\frac {7!}{2!3!2!} = 210\) 種放法。
抽象來說，我們將 \(k\) 個元素進行排列，對于第 \(i\) 個元素一共有 \(x_i\) 個。那么總的排列方案數為
組合
其實就是順序無關的排列
定理：具有 \(n\) 個元素的集合，選出 \(r\) 個數組成新的集合，本質不同的集合數為
\[C(n,r) = {n \choose r} = \frac {n!}{r!(n-r)!} \]
由于順序無關，我們考慮通過排列推導。
證明：為了得出所有集合，我們先考慮順序相關，也就是有 \(P(n, r)\) 個排列，而對于每一個排列，如果不考慮順序，一共重復計算了 \(P(r, r)\) 次，所以
性質
接下來我們考慮組合的各種性質
\[{n \choose m} = {n \choose n - m} = \frac nm {n - 1 \choose m - 1} = {n-1 \choose m} + {n - 1 \choose m - 1} \]
-
前兩個等式，考慮按照定義展開化簡即可
-
考慮最后一個等式，
其實就是楊輝三角的遞推，我們欽定 \(n\) 中的一個元素，分情況討論-
如果不選擇這個數，也就是在剩下的數中選擇 \(m\) 個數，那么一共有 \({n-1 \choose m}\) 種情況
-
如果選擇這個數，那么只需要在剩下的數種選擇 \(m - 1\) 個數即可，那么一共有 \(n - 1 \choose m - 1\) 種情況
-
\[\binom nk \binom km = \binom nm \binom {n-k}{m-k} \]
證明：展開即可
\[\sum_{i=k}^n \binom ik = \binom {n+1}{k+1} \]
證明：還是考慮展開
\(\binom k {k+1}\) 是不合法的，所以其值為 0，加上去之后不會對結果產生影響
我們通過公式 \(\binom nm = {n-1 \choose m} + {n - 1 \choose m - 1}\) 兩兩合并即可。
推論：我們將 \(i\) 平移，那么得出
\[\sum_{i=0}^n i \binom ni = n 2^{n-1} \]
證明：
考慮代數展開，通過 \({n \choose m} = {n \choose n - m}\) 變化即可。
但是，其實可以通過生成函數推導。推導步驟如下：
生成函數可以參考另外一篇博客：普通型生成函數 - Ricky2007 - 博客園
我認為講的不錯
我們先展開，得到
我們可以由此聯想到生成函數求導的公式
那么我們考慮求導前的生成函數序列：
顯然，其生成函數展開之前為 \(F(x) = (1+x)^n\)
那么我們對其求導得到 \(F'(x) = n(1+x)^{n-1}\)
展開之后為
我們考慮需要把所有的系數加起來，那么我們令 \(x = 1\) 即可
所以，得出
我們考慮擴展一下上述式子
\[\sum_{i=0}^n i^2 \binom ni = n 2^{n-1} + (n-1)n2^{n-2} \]
考慮還是利用生成函數的思路。
將生成函數 \(F'(x) = n(1+x)^{n-1}\) 向右平移一位并再次求導：
那么我們還是借上面的思路，令 \(x = 1\)，所以
二項式定理
定理：令 \(n\) 是非負整數，那么有
\[\begin{aligned} (x+y)^n & = \sum_{i = 0}^n x^{n - i}y^i \\ & = \binom{n}{0}x^ny^0 + \binom n1 x^{n-1}y^1 + \cdots + \binom n {n-1} x^1y^{n-1} + \binom nn x^0 y^n \end{aligned} \]
考慮展開之后每一項都應該是 \(n\) 次的，所以 \(x\) 為 \(i\) 次一共有 \(\binom ni\) 種情況
我們利用這個找到一些有用的性質：
推論：令 \(n\) 為非負整數，那么
\[\sum_{i=0}^n \binom ni = 2^n \]
證明：用二項式定理，令 \(x = y = 1\)，那么
推論：令 \(n\) 為非負整數，那么
\[\sum_{i=0}^n (-1)^i \binom ni = 0 \]
證明：令 \(x = -1, y = 1\) 即可
范德蒙卷積
已知 \(n, m, t\)
\[\sum_{i=0}^t \binom ni \binom m {t-i} = \binom{n + m} t \]
證明：在組合意義上，相當于在 \(n\) 中選 \(i\) 個，在 \(m\) 中選剩下的，也就是在 \(n + m\) 中選擇 \(t\) 個。
而二項式證明這里就不展開了。
例題
請證明：
\[\sum_{i=0}^n {\binom ni}^2 = \binom {2n} n \]
Lucas定理
定理：
\[\binom nm \equiv \binom {\lfloor \frac np \rfloor}{\lfloor \frac mp \rfloor} \binom {n \% p}{m \% p} \pmod p \]這個證明相對復雜，請酌情食用
證明：
我們考慮通過帶余方程改寫上述式子：
我們通過生成函數 \(F(x) = (1+x)^{sp+t}\) 的第 \(kp+r\) 次項的系數求。
我們先求一個推導的時候需要的東西：
那么我們正式開始推導：
我們取 \(x^{kp+r}\) 項
那么當且僅當 \(i = k, j = r\) 時，就可以取出 \(x^{kp+r}\) 項的系數。
考慮為什么當且僅當？
可知，我們需要 \(ip+j = kp + r\)
\[\begin{aligned} & \because j \in [0, t], t \in [0, p), r \in [0, p) \\ & \therefore j = r, i = k \end{aligned} \]
那么，其系數為
所以，可知
得證：
程序實現：
這里還是稍微講一下吧
首先，我們需要求出組合數，那么我們先預處理一下模數以內的階乘和階乘逆元：
long long fac[N] = {1}, ifac[N];
for (int i = 1; i < MOD; ++i) fac[i] = (i * fac[i - 1]) % MOD;
ifac[MOD - 1] = quickPow(fac[MOD - 1], MOD - 2, MOD);
for (int i = MOD - 1; i; --i) ifac[i - 1] = ifac[i] * i % MOD;
考慮一下組合數的特殊情況，如果 \(n < m\) 那么 \(\binom nm = 0\)
所以我們求模數以內的組合數方法如下：
inline int C(int i, int j) {
if (i > j) return 0;
return fac[j] * ifac[i] % MOD * ifac[j - i] % MOD;
}
那么Lucas定理呢？我們處理一下 \(n = 0\) 的特殊情況即可
inline int Lucas(int i, int j) {
if (i == 0) return 1;
return Lucas(i / MOD, j / MOD) * C(i % MOD, j % MOD) % MOD;
}
廣義容斥與二項式反演
這個部分相對較復雜，我給出反演公式
令 \(f_n\) 表示之多擁有 \(n\) 個屬性的集合個數，\(g_n\) 表示恰好擁有 \(n\) 個屬性的集合
那么
反演推導證明