组合数学常用公式

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15690256.html

组合数学的推式子题公式基本上都有了

$$\Large\sum_{i=0}^nC_n^i=2^n$$

$$\Large\sum_{i=0}^nC_n^i(-1)^i=0$$

$$\Large\sum_{i=0}^nC_n^ix^i=(1+x)^n$$

$$\Large C_n^kC_k^i=C_n^iC_{n-i}^{k-i}=$$

(上面这条可以和第一条公式结合用)

$$\Large C_n^i=C_{n-1}^{i-1}+C_{n-1}^i=C_{n-1}^{i-1}+C_{n-2}^{i-1}+C_{n-2}^i=...=\sum_{j=i-1}^{n-1}C_{n-1}^{i-1}$$

$$\Large C_{n+1}^{k+1}=\sum_{i=k}^nC_i^k$$

$$\Large C_{n+1}^{k+1}=\sum_{i=k}^nC_{i-k}^i$$

\Large\sum_{i=0}^kC_{n+1}^i$=2\times\sum{i=0}^kC_n^i-C_n^k

卢卡斯定理（$p$ 为质数）：

$$\Large C_m^n\bmod p=C_{m/p}^{n/p}\times C_{m\bmod p}^{n\bmod p}$$

二项式定理：

$$\Large(a+b)^n=\sum_{i=0}^nC_{n}^ia_ib_{n-i}$$

范德蒙公式：

$$\Large\sum_{i=0}^nC_n^iC_m^i=C_{n+m}^n=C_{n+m}^m$$

$$\Large\sum_{i=0}^kC_n^iC_m^{k-i}=C_{n+m}^k$$