组合数公式

组合数公式

---

组合数$\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) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

---

$… \ \cdot C(n,i)$型

$\displaystyle \sum i \cdot C(n,i)$

$\displaystyle = \sum {i \cdot \frac{n!} {i! \cdot (n-i)!} }$

$\displaystyle = \sum { \frac{n!} {(i-1)! \cdot (n-i)!} }$

$\displaystyle=\sum {n \cdot \frac {(n-1)!} {(i-1)! \cdot (n-i)!} }$

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

同理的

$$\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) \mod p = C(n \mod p,m \mod p) \cdot C(\lfloor\frac{n} {p}\rfloor, \lfloor \frac{m} {p}\rfloor) \mod 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)$

$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)$

又$\because S(n,m)+S(n,m+1)=2S(n,m+1)-C(n,m+1)$

$\therefore S(n,m)=2S(n-1,m)-C(n-1,m)$

(待补。。。)