会把集训笔记抽时间整合到省选/NOI 数学的文章上。
讲师：施开成，CTSC 第五名。
组合数学
\(C_n^m\) 表示在 \(m\) 个数中选 \(n\) 个数的方案数，狭义的要求 \(n\ge m\ge 0\)，\(n,m\) 均为正整数。
也叫二项式系数。
对于实数 \(a\) 和非负整数 \(n\)，定义下降幂 \(a^{n_{_}}\)，等于 \(a(a-1)\cdots (a-n+1)\)。
发现 \(a^{*}=\frac{a!}{(a-n)!}\)。
组合数公式：\(\frac{m!}{n!(m-n}!}\)。
\(C_n^m=C_{n-m}^m\)，\(C_n^m=C_m^{n-1}+C_{m-1}^{n-1}\)，\(mC_n^m=nC_{n-1}^{m-1}\)，依据组合数公式推导。
\(\sum_{m=1}^mmC_n^m\)，这就可以用吸收公式+二项式定理做。
\(C_a^b\times C_b^c=C_a^c\times C_{a-c}^{b-c}\)。
\(\sum\limits_{i=a}^bC_i^a=C_{b+1}^{a+1}\)。
证明：在等式左侧添加 \(C_a^{a+1}\)，然后吸收公式做，\(C_a^{a+1}=0\)，虽然不是良定义。
\(\sum\limits_{i=0}^nC_{a+i}^i=C_{a+n+1}^n\)。
二项式定理
\((a+b)^n=\sum\limits_0^nC_n^ia^ib^{n-i}\)
发现这样的乘法相当于从前面挑一项，从后面挑一项相乘，最后加起来。
对于 \(n\) 次多项式，挑到 \(i\) 个 \(a\) 的方案数是 \(C_n^i\)。
系数和等价于杨辉三角一行的求和，为 \(2^n\)。
广义二项式略去。
感觉很厉害，听不懂。
范德蒙德卷积恒等式
\(\sum\limits_{i=0}^aC_n^i\times C_m^{a-i}=C_{n+m}^a\)
组合意义考虑？
多项式？
上指标范德蒙德卷积恒等式
\(\sum\limits_{i=a}^{n-b}C_i^a\times C_{n-i}^b=C_{n+1}^{a+b+1}\)
不会不会不会不会不会。
把 \(n\) 个一样的球放到 \(m\) 个不同的盒子中，一个盒子可以放多个球或不放球，求总方案数。
隔板法，看上去很经典。
将 \(n\) 个球中间放 \(m-1\) 个隔板，放隔板的方案数为 \(C_{n+m-1}^{m-1}\).
每个变量有下界 \(x_i\ge a_i\)，问满足 \(\sum\limits_1^nx_i=k\) 的整数解的数量。
将每个变量视作盒子，然后和上面一样。
有 \(m\) 个不同的树苗和 \(n\) 个坑，需要把所有树苗放入坑中，要求一个坑至多一个树苗，没有两个树苗在相邻的坑中，求方案数。
把 \(m\) 颗树苗将这 \(n\) 个坑分成 \(m+1\) 段的每段长度看作变量，左右两边下界 \(0\)，中间下界 \(1\)。
从 \(n\) 个不同的物品中取出 \(m\) 个排成一个环，求方案数。
有 \(k\) 中不同的元素，地 \(i\) 中有 \(a_i\) 个，求将这些元素排成一列的方案数。
先认为每种 \(a_i\) 的元素互不相同，答案为 \(\frac{(\sum a_i)!}{\prod a_i!}\)。
如果将二项式定理中的幂改成下降幂仍然成立。
证明考虑数学归纳法。听不懂。
标签：方案,树苗,limits,sum,day1,数学,整合,二项式,times From： https://www.cnblogs.com/BYR-KKK/p/-/math_index