【总结】组合模型及其组合意义的阐释
==重要说明：本文统一使用"球和格子"模型阐释组合意义。==
(这种东西)极具启发性，有助于人们深刻理解组合数学。——卢华明
可重组合
描述
有\(m\)种球每种球都是足够多的，有\(n\)个盒子，现在要把盒子塞满(一种球可以用多次)，多少种方案？
公式
\[ f_0(n,m)={{m+n-1}\choose n} \]
组合阐释1(构造法)
不失一般性，把球编号，然后按照从小往大排序，设第\(i\)位置上面为\(a_i\)，构造一个新的数列\(b_i=a_i+i\)，很显然\(b_i\)是互不相同的。我们知道\(b_i \in [1+1,n+m]\)的，所以问题就变成了从\([2,n+m]\)中选出\(n\)个数，显然这个的方案数就是\(\begin{pmatrix}m+n-1\\n\end{pmatrix}\) 个。
组合阐释2(一一对应法)
从2到\(m+n\)任意选出\(n\)个数，即\(\begin{pmatrix}m+n-1\\n\end{pmatrix}\)方法，这些取的方法和可重组合的方法一一对应。具体对应方式是对于取出来的第\(i\)小数减去\(i\)，这样得出来的新数列的范围就在\([1,m]\)的范围内，并且新数列会有相同的元素，对应的就是选了几个相同元素。
拓展套路1
盒子有编号怎么办？
\[
f_1(n,m)= A_{m+n-1}^{n}={{m+n-1}\choose n}\times n!
\]
之前的盒子是没有编号的，现在的盒子有编号了，之前每一种无序的安排都可以对应到\(n!\)个有序安排内。
拓展套路2
盒子可以不放满怎么办？
解法1
\[ f_2(n,m)=\sum_{i=1}^{n}{n\choose i}{f_0(m,i)} \]
过于显然不解释。
解法2
相当于多了一个球，我们把这个球叫做"无球"，选择这个球代表盒子是空的。所以：
\[
f_2(n,m)=f_0(n+1,m)
\]
这就给了我们一个可重组合的递推公式(滑稽)
拓展套路3
球有个数限制怎么办？
\(O(2^n)\)容斥。
\[
f_3(n,m)=\sum_{s \sube S} (-1)^{|s|}f_2(n+1,m-\sum_{i\in s}(a_i+1))
\]
相当于钦定一些球至少选择\(a_i+1\)个使得它们一定选多了，然后容斥原理即可。
拓展套路4(真的拓展)
要求这些某种球只能选择它给定集合\(S_i\)内的数怎么办？
\[
\prod_{i=1}^{m}\sum_{j\in S_i}x^j
\]
的\(n\)项系数
拓展套路5(画蛇添足)
我想算复杂一点怎么办？
\[
\prod_{i=1}^{m}\sum_{j=1}^{\infin}x^j=(\frac{x}{1-x})^m
\]
的\(n\)项系数...
其实可以用来多项式优化。
不相邻组合
描述
有\(n\)个球，\(m\)个盒子，(注意看，这里和之前的表述不同了)选出的球不能相邻，有多少种组合方式？
公式
\[ f_0(n,m)={{n-m+1}\choose{m}} \]
组合阐释1
从\([0,n-m]\)中选出\(m\)个数，将第\(i\)小的数加上\(i\)构成新的序列，新的序列在\([1,n]\)的范围内，并且不会重复。
拓展套路1
可重不相邻组合？
我不太会\(O(1)\)，貌似会\(O(n)\)
\[
\sum_{i=1}^n{n-i+1\choose i}{i+m-1\choose m}
\]
就这么过掉了，毕竟不知道什么..
格路模型
从坐标原点走到\((n,m)\)的方案数是
\[
{{n+m}\choose n}
\]
组合阐释1
从原点走到\((n,m)\)一定要走\(n+m\)步，从\(n+m\)次走步(大雾)中选出\(n\)种往上走就对应了每一种走路的方法。
比yyb在NOIP集训专题分享上在讲台上讲的好多了
组合阐释2
设\(dp(i,j)\)表示从原点走到\((i,j)\)的方案:根据加法原理
\[
dp(i,j)=dp(i-1,j)+dp(i,j-1)
\]
而由组合数递推公式
\[
{{m+n}\choose n}={{m+n-1}\choose n-1}+{{m+n-1}\choose n}
\]
记\(f(n,m)={{m+n}\choose n}\)
则有
\[
f(n,m)=f(n-1,m)+f(n,m-1)
\]
和上上式一样。
格路是我们重要的思维方式，也是重要的证(gan xing)明(li jie)方式。
艾提艾斯提模型
别看这个名字
等式:
\[
{{n+m+1}\choose m}={{n+m}\choose m}+\sum_{i=1}^m {n+m-i\choose m-i}
\]
组合阐释1(格路)
\(\begin{pmatrix} n+m+1\\m\end{pmatrix}\):从原点到\((n+1,m)\)的方案数
\(\begin{pmatrix} n+m \\ m \end{pmatrix}\):从原点到到\((n,m)\)的方案数
\(\begin{pmatrix} n+m-i \\ m-i \end{pmatrix}\):从原点到\((n,m-i)\)的方案数
又因为，从原点到\((n+1,m)\)的路径方案数是这样构成的
蓝色到蓝色点的路径显然由所有黑色点贡献
所以就证完了。
备胎模型
考虑一个这样的恒式子
\[
{n \choose l}{l \choose r}={n \choose r}{n-r\choose l-r},l\in[r,n]
\]
组合阐释1
考虑从\(n\)选出\(l\)个再从\(l\)选出\(r\)个和直接$\begin{pmatrix} n \r \end{pmatrix} $有什么区别？？
当然是有的，因为有\(n-r\)个你选出来的最后没要...
所以选出这\(n-r\)个炮灰也是会造成方案的不同啊
所以上面这个式子的组合意义就很清晰了
扩展套路1
多选几轮？
\[
{n \choose l}{r\choose q}{q\choose m}={n-q\choose l-q}{n-m\choose q-m}{n \choose q}
\]
找规律大法好 \((n=a_0)\)
\[
\prod_{i=1}^k{a_{i-1}\choose a_i}={a_0\choose a_k}\prod_{i=1}^{k-1}{a_0-a_i\choose a_i- a_{i+1}}
\]
奇偶模型
\[ \sum_{i=0} ^n(-1)^i{n \choose i}=0 \]
注意到上式也说明了对于\((-1)^{i+1}\)也是成立的。
直接证明1
\[ (x+y)^n= \sum_{i=0}^n {n \choose i}x^iy^{n-i} \]
令\(x=1,y=-1\)证毕。
(没有营养的)
组合阐释1
上式相当于不停从\(n\)中选个子集出来(包括空集)，然后把所有集合的大小为偶数的方案加起来，把所有集合的大小为奇数的方案加起来，然后相减。
所以我们只要建立起一个奇子集和分成偶子集的各种方案之间建立一个一一对应的关系就好了。
一一对应很显然吧...
分析随便某个元素\(x\)，它只有两种状态:在分出来的子集内，不在分出来的子集内。对于一个任何一个给定的集合，我们就直接把\(x\)是否存在的这个布尔条件!一下，然后就改变了这个集合的奇偶性，而且新增的方案也是合法的。这样就一一对应起来了。
黑白模型
考虑恒等式
\[
{m+n\choose r} =\sum_{i=0}^r {m\choose i}{n\choose r-i}, r\le m \le n
\]
组合阐释1
分成\(m\)个黑球和\(n\)个白球，从\(m+n\)个球里选出\(r\)个无外乎从黑球选\(i\)个再从白球中选\(r-i\)个。