组合数公式

---

组合数 \(\displaystyle C(n,m)=C_n^m=\binom{n}{m}\).

递推式

\(C(n,m)=C(n-1,m-1)+C(n-1,m)\).

---

组合数完全累和

\(\displaystyle \sum_{i=0}^n C(n,i) =2^n\).

---

奇偶累和

\(\displaystyle \sum_0^n (-1)^i C(n,i)=[n=0]\).

---

\(\sum\cdots\sum \rightarrow C()\) 型

我们熟知的有：

\(\displaystyle \sum_{i=1}^{n}1=n = C(n,1)\)

\(\displaystyle\sum _{i=1}^{n} \sum_{j=i+1}^{n} 1= \frac{n(n-1)}{2}\)

更一般的：

\(\displaystyle\underbrace {\sum \sum ... \sum} 1 =C(n,k)\)

\((k个\sum) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)

---

$ ...  C(n,i)$ 型

\[ \begin{aligned} &\sum i \cdot C(n,i) \\ =& \sum {i \cdot \frac{n!}{i! \cdot (n-i)!}} \\ =& \sum { \frac{n!}{(i-1)! \cdot (n-i)!}} \\ =&\sum {n \cdot \frac {(n-1)!} {(i-1)! \cdot (n-i)!}} \\ =&n\cdot \sum C(n-1,i-1) \end{aligned} \]

同理的：

\(\sum i\cdot (i-1)\cdot C(n,i)=n \cdot (n-1) \cdot \sum C(n-2,i-2)\)

带入还能得到：

\(\sum i^2 \cdot C(n,i) = n \cdot (n-1) \cdot \sum C(n-2,i-2)+n \cdot \sum C(n-1,i-1)\)。

更一般的，可以表示成 \(\sum C(i,k) \cdot C(n,i) =C(n,k) \cdot \sum C(n-k,i-k)\)。

---

多组合数相乘型

\(\displaystyle \sum_{i=0}^{k} C(n,i)\cdot C(m,k-i) = C(n+m,k)\)

其实就是两个组合问题的组合，可以直接通过实际意义得到

---

Lucas定理

$ C(n,m) p = C(n p,m p) C( {p}, {p}) p$

预处理阶乘逆元后，可以用于解决模数较小而\(n,m\)较大的组合数问题

---

前缀和

列

\(\displaystyle \sum_{i=0}^n \binom{i}{m}=\binom{n+1}{m+1}\)

由递推式 \(\displaystyle \binom{i}{m}=\binom{i-1}{m}+\binom{i-1}{m-1}\) 容易迭代发现：

行

令 \(S(n,m)=\sum_{i=0}^{m} C(n,i)\)

\[ \begin{aligned} &S(n,m)+S(n,m+1) \\ =&\sum_{i=0}^{m}(C(n,i)+C(n,i+1))+C(n,0) \\ =&\sum C(n+1,i+1)+C(n,0) \\ =&S(n+1,m+1) \end{aligned} \]

又 \(S(n,m)+S(n,m+1)=2S(n,m+1)-C(n,m+1)\)，故 \(S(n,m)=2S(n-1,m)-C(n-1,m)\)。

(待补。。。)