<学习笔记>组合数学

#### 插板法

问题一：现有 $n$ 个 完全相同的元素，要求将其分为 $k$ 组a，保证每组至少有一个元素，一共有多少种分法？

考虑拿 $k-1$ 块板子插入到 $n$ 个元素两两形成的 $n-1$ 个空里面。

所以答案就是
$$\binom{n-1}{k-1}$$

问题二：如果问题变化一下，每组允许为空呢？

显然此时没法直接插板了，因为有可能出现很多块板子插到一个空里面的情况，非常不好计算。

我们考虑创造条件转化成有限制的问题一，先借 $k$ 个元素过来，在这 $n+k$ 个元素形成的 $n+k-1$ 个空里面插板，答案为
$$\binom{n+k-1}{k-1}$$

再思考一下，若是从 $n$ 个数字中选可重复的 $m$ 个数的方案数，这与问题二类似

我们把 $m$ 个元素中插入 $n−1$ 个隔板，我们从这 $n+m−1$ 个元素中选 $n−1$ 个元素作为隔板,第 $i−1$ 个隔板和第 $i$ 个隔板之间的元素个数即为第 $i$ 个数字所选的个数。也就是将 $m$ 个元素分为 $n$ 组，且可以为空。

$$\dbinom{m+n-1}{n-1}$$

#### 组合恒等式
##### 1
$$\dbinom{n+m-1}{n-1}$$

$m$ 的补集与 $m$ 的方案数是相同的。

##### 加法公式
$$\dbinom n m=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}\tag{2}$$
组合推理:考虑选不选第 $n$ 个，不选的情况为 $\dbinom{n-1}{m}$ ，选的情况为 $\dbinom{n-1}{m-1}$

##### 上指标求和法则

$$\sum\limits^n_{i=0}\dbinom ik=\dbinom{n+1}{k+1}\tag{13}$$

可以利用加法公式，通过归纳法证明

$$\dbinom{5}{3}$$
$$=\dbinom{4}{2}+\dbinom{4}{3}$$
$$=\dbinom{4}{2}+\dbinom{3}{2}+\dbinom{3}{3}$$
$$=\dbinom{4}{2}+\dbinom{3}{2}+\dbinom{2}{2}+\dbinom{2}{3}$$
$$=\dbinom{4}{2}+\dbinom{3}{2}+\dbinom{2}{2}+\dbinom{1}{2}+\dbinom{1}{3}$$
$$=\dbinom{4}{2}+\dbinom{3}{2}+\dbinom{2}{2}+\dbinom{1}{2}+\dbinom{0}{2}+\dbinom{0}{3}$$

现在 $\dbinom{0}{3}$ 为零，所以不需要再推，其实$\dbinom{0}{2}$ $\dbinom{1}{2}$ 也为零，但保留的话可以清晰看出一般形式。

组合推理：在 $n+1$ 个球里拿 $k+1$ 个为$\dbinom{n+1}{k+1}$，最后一个拿的是第 $i$ 个，则情况数为 $\dbinom ik$,累加即为所求。

##### 平行求和法

$$\sum\limits^n_{i=0}\dbinom {m+i}i=\dbinom{n+m+1}{n}\tag{14}$$

证明：
$$\begin{aligned}
\sum\limits^n_{i=0}\dbinom {m+i}i&=\sum\limits^n_{i=0}\dbinom {m+i}m\\
&=\sum\limits^{n+m}_{i=m}\dbinom {i}m+0\\
&=\sum\limits^{n+m}_{i=m}\dbinom {i}m+\sum\limits^{m-1}_{i=0}\dbinom {i}m\\
&=\sum\limits^{n+m}_{i=0}\dbinom im\\
&=\dbinom{n+m+1}{m+1}=\dbinom{n+m+1}{n}
\end{aligned}$$

给道例题 BZOJ 4403序列统计