数学 · 组合数学基础
lg_zhou
·
·
个人记录
罕见的不难的数学
组合数相信大家都不陌生，基础定义也不再阐释。
性质：
-
C^m_n = C^{n-m}_n
- 证明：显然成立。选出 m 个数和选出 n-m 个不选的数是等价的。
-
C^m_n = C^{m}_{n-1}+C^{m-1}_{n-1}
- 证明：简单的递推。考虑第 n 个物品到底选不选，选的话就是剩下 n-1 个中选 m-1 个，是 C^{m-1}_{n-1} ，不选同理，是 C^{m}_{n-1}。答案是两者相加。
-
C^1_n+C^2_n+C^3_n+......C^n_n = 2^n
- 证明：显然，因为左右都可以表示 n 个物品取任意多个的方法数。
二项式定理：
(a+b)^n = \sum\limits_{i=0}^nC_n^ia^ib^{n-i}
- 证明：考虑数学归纳法。当 n=1 时，上式显然成立。我们假设 n=m 时成立，只要证明 n=m+1 时成立即可。
那么：(a+b)^{m+1} = (a+b)(a+b)^m = (a+b)\sum\limits_{i=0}^mC_m^ia^ib^{m-i}
把 a,b 乘进去 ：=\sum\limits_{i=0}^mC_m^ia^{i+1}b^{m-i}+\sum\limits_{i=0}^mC_m^ia^ib^{m-i+1}
再把指数统一一下：=\sum\limits_{i=1}^{m+1}C_m^{i-1}a^{i}b^{m-i+1}+\sum\limits_{i=0}^mC_m^ia^ib^{m-i+1}
最后用上面的性质二进行合并：
=\sum\limits_{i=0}^{m+1}(C_m^{i-1}+C_m^i)a^{i}b^{m-i+1} =\sum\limits_{i=0}^{m+1}(C_{m+1}^i)a^{i}b^{m-i+1}
卢卡斯定理：
C^n_m\equiv{C^{n\bmod p}_{m\bmod p}*C^{n/p}_{m/p}\pmod{p }}
后续：如果出现了 n 类物品，并且第 i 类有 a_i个 , 要取 m 个物品，求方案总数，要怎么算呢？
请看 可重集的组合计数。