集合与重集
集合相关计数
令 $S=\{x_1,a_2,..,x_n\}$ 是一个有 $n$ 个元素的集合。
子集个数——双射法简单例子
令 $2^{S}$ 表示所有 $S$ 的子集组成的集合，现在我们想要知道 $|2^{|S|}|$。
通过二项式定理的简单推导，我们可以很轻松地得到：
$$
|2^{|S|}|=\sum_{i=0}^n\binom{n}{i}=(1+1)^n=2^n
$$
但如果我们现在不知道二项式系数这一强大的工具，我们应该如何给出一个组合证明？
考虑 $\{0,1\}^n=\{(\mathcal{E_1},\mathcal{E_2}…,\mathcal{E_n})|\mathcal{E_i\in\{0,1\}}\}$，因为每个 $\mathcal{E_i}$ 有两种取值，因此，根据乘法原理 $|\{0,1\}^n|=2^n$。
定义映射 $\theta(T)$ 是从 $2^S$ 到 $\{0,1\}^n$ 的映射，$\theta(T)=(\mathcal{E_1},\mathcal{E_2}…,\mathcal{E_n})$，若 $x_i\in T,\mathcal{E_i}=1$,若 $x_i\not\in T,\mathcal{E_i}=0$。
显然 $\theta$ 是一个双射，因此 $|2^S|=|\{0,1\}^n|=2^n$ 。
从生成函数的角度考察二项式系数
设 $x_1,x_2,…,x_n$ 为独立的不定元：
$$
\prod_{i=1}^n(1+x_i)=\sum_{S\subseteq T}\prod_{x_i\in S} x_i
$$
当任意 $x_i=x$ 时：
$$ (1+x)^n=\sum_{S\subseteq T}x^n=\sum_{i\ge 0}\binom{n}{i}x^i $$
上式成立的原因是和组合结构符号化中本质一样的两种生成函数表示方法：
若 $\ell$ 为由有限个集合组成的集族，且恰好包括 $f(n)$ 个 $n$ 元集合：
$$
\sum_{S\in \ell} x^{|S|}=\sum_{n\ge 0}f(n)x^n
$$
令$g:\mathbb{N}\to \mathbb{C}$，那么有：
$$
\sum_{S\in \ell}g(|S|)x^{|S|}=\sum_{S\in \ell} g(n)f(n)x^n
$$
集合的子集与整数的有序分拆
$n$ 的一个有序分拆是指将 $n$ 表示为一些有序的正整数之和。
如果在一个有序分拆 $\sigma$ 中有正好有 $k$ 个求和项，我们称 $\sigma$ 有 $k$ 个部分，并称 $\sigma$ 为一个 $k$ - 有序分拆。
如果 $\sum_{1\le i\le k}a_i$ 是 $n$ 的一个 $k$ - 有序分拆，我们定义映射
$\theta(\sigma)=\{a_1,a_1+a_2,…,\sum_{1\le i\le k-1}a_i\}$。
即 $\sigma$ 前 $k-1$ 项求和项的前缀和构成的集合。
因为 $\sum_{1\le i\le k}a_i=n$ 所以集合中的每一项一定严格小于 $n$，且不同的有序拆分一定对应着不同的集合 （不同序列的前缀和序列一定互不相同）。
因此 $\theta$ 一定是从所有 $k$ - 有序分拆方案构成的集合到 $[n-1]$ 的所有 $k-1$ 元子集构成的集合的单射。
且我们发现其一定也是一个满射，因此 $\theta$ 一定是双射。
因此 $n$ 的 $k$ - 有序分拆有 $\binom{n-1}{k-1}$ 个。
其有一个更广为人的名称——插板法，插板法和不定方程的解的关系已经在 组合数学与计数入门学习笔记 有所讨论。
重集相关计数
可重组合数与重集
这里的定义比较多 直接引用原书：
可重组合数的组合证明
我们显然可以把可重组合数与不定方程整数解之间建立联系，这里给出一个严谨的组合证明。
令 $1\le a_1 < a_2 < a_3… < a_k\le n+k-1$ 为 $[n-k+1]$ 的一个 $k$ 元子集，令 $b_i = a_i-i+1$ 则 $b_i$ 对应着 $[n]$ 上一个 $k$ 元重集。
同样地，对于 $[n]$ 上的一个 $k$ 元重集 $1\le a_1\le a_2 …\le a_k\le n$ 令 $b_i = a_i + i - 1$ ，其对应着 $[n-k+1]$ 的一个 $k$ 元子集。
这样，我们就在两者间建立了双射。
可重组合数生成函数角度的探讨
$$ \begin{array}{l} \left(1+x_{1}+x_{1}^{2}+\cdots\right)\left(1+x_{2}+x_{2}^{2}+\cdots\right) \cdots\left(1+x_{n}+x_{n}^{2}+\cdots\right) \\\ =\sum_{\nu: S \rightarrow \mathbb{N}} \prod_{x_{i} \in S} x_{i}^{\nu\left(x_{i}\right)} \end{array} $$
$x_i=x$
$$ \begin{aligned} \left(1+x+x^{2}+\cdots\right)^{n} &=\sum_{\nu} x^{\nu\left(x_{1}\right)+\cdots+\nu\left(x_{n}\right)} \\\ &=\sum_{S\text { 上的 } M} x^{|M|}\\\ &=\sum_{k \geq 0}\left(\left(\begin{array}{l} n \\\ k \end{array}\right)\right) x^{k} \end{aligned} $$
$$ \left(1+x+x^{2}+\cdots\right)^{n}=(1-x)^{-n}=\sum_{k \geq 0}\left(\begin{array}{c} -n \\\ k \end{array}\right)(-1)^{k} x^{k} $$
因此
$$ \left(\left(\begin{array}{l} n \\\ k \end{array}\right)\right)=(-1)^{k}\left(\begin{array}{c} -n \\\ k \end{array}\right) = \binom{n+k-1}{k} $$
