：排列三程序

1 排列组合1.1 排列

[A_n^m=n(n-1)(n-2)cdots(n-m+1)=frac{n!}{(n-m)!} ]

1.2 组合

[C_n^m=frac{A_n^m}{m!}=frac{n!}{m!(n-m)!}]

二项式定理

[(a+b)^n=sum_{i=0}^{n}binom{n}{i}a^{n-i}b^i ]

[当 n=1 时，a+b= sum_{i=0}^1binom{1}{i}a^{1-i}b^i=binom{1}{0}a^1b^0+binom{1}{1}a^0b^1=a+b ,公式成立]

[假设n=m 时公式成立，设n=m+1，则有： ]

[(a+b)^{m+1}=a(a+b)^m+b(a+b)^m ]

[= asum_{i=0}^mbinom{m}{i}a^{m-i}b^i+bsum_{j=0}^mbinom{m}{j}a^{m-j}b^j]

[= sum_{i=0}^mbinom{m}{i}a^{m+1-i}b^i+sum_{j=0}^mbinom{m}{j}a^{m-j}b^{j+1},提出当i=0时和当j=m时的项]

[= a^{m+1}+ sum_{i=1}^mbinom{m}{i}a^{m+1-i}b^i +b^{m+1} +sum_{j=0}^{m-1}binom{m}{j}a^{m-j}b^{j+1} ，令j=i-1]

[= a^{m+1} +b^{m+1}+ sum_{i=1}^mbinom{m}{i}a^{m+1-i}b^i+sum_{i=1}^{m}binom{m}{i-1}a^{m+1-j}b^i ]

[=a^{m+1} +b^{m+1}+ sum_{i=1}^mBigg[binom{m}{i}+binom{m}{i-1}Bigg]a^{m+1-i}b^i,根据：binom{n}{m}+binom{n}{m-1}=binom{m+1}{i}]

[=a^{m+1} +b^{m+1}+ sum_{i=1}^mbinom{m+1}{i}a^{m+1-i}b^i ]

[= sum_{i=0}^{m+1}binom{m+1}{i}a^{m+1-i}b^i ]

Lucas 定理

若 p 是质数，则对于任意整数 $ 1 le m le n $ 有：

[binom{n}{m} equiv binom{n ~ mod ~ p}{m ~ mod ~ p}binom{n/p}{m/p} (mod~p)]

证明较难，需要用到生成函数的知识，有兴趣的可以看看。别问我，我也不会。

使用这个公式就可以对较为麻烦的组合数进行取模。

鸽巢定理

[若有 sum_l equiv sum_r~(mod~c) ]

[即 sum_l -sum_requiv0 ~(mod~c)]

[那么 sum_{i=l+1}^ra_iequiv0 ~(mod~c) ]

[所以sum_{i=l+1}^ra_i 即为解]

[前缀和的个数为 n ,模 c 的情况下去除为0的情况，总共有 c-1 种情况，n>c-1 ]

[根据鸽巢定理 一定有 sum_l equiv sum_r~(mod~c) ]

[综上所述：该题恒有解，解为{ a_{l+1},a_{l+2},cdots ,a_r |sum_l equiv sum_r~(mod~c) } ]

容斥定理另外

组合数还有很多内容比如：

这些都是一些经典计数模型，可以不用会证明或者推导，但是要知道他们能解决什么类型的问题，他们的模型是什么。

如果对组合计数很感兴趣，可以学下生成函数（母函数）