引用一道题目名：

$\operatorname{Combinatorics} ~\operatorname{Is} ~\operatorname{Fun}$

先放一下神犇 $\operatorname{i\color{red}{x35}}$ 的博客：NOI 一轮复习 IV：组合计数

排列数

从 $n$ 个不同的物体中有序的选择 $k$ 个有多少种方案？

$n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) = \dfrac{n!}{(n-k)!}$

组合数

从 $n$ 个不同的物体中无序的选择 $k$ 个有多少种方案？

$k$ 个不同的物体有 $k!$ 种排列的方案
因此一个无序的选择方案恰好对应 $k!$ 个有序的选择方案。

$\dfrac{n \times (n-1) \times \cdots \times (n-k+1)}{k!} = \dfrac{n!}{k!(n-k)!}$

记做 $\dbinom{n}{k}$

二项式系数

在 $(x+1)^n$ 中，$x^k$ 的系数是什么？

容易发现，这等价于在 $n$ 个单项式内选 $k$ 个取 $x$，其余取 $1$。因此答案恰为 $\dbinom{n}{k}$
即 $(x+1)^n = \displaystyle\sum_{k=0}^n \dbinom{n}{k}x^k$

二项式定理

$(a+b)^n = \displaystyle\sum_{i=0}^n \dbinom{n}{i} a^{n-i}b^i$

推论式：$\displaystyle\sum_{i=0}^n (-1)^i \dbinom{n}{i} = [n = 0]$

广义二项式系数

如果 $\alpha$ 不是正整数，当 $(x+1)^{\alpha}$ 展开为幂级数后 $x^k$ 的系数是什么？

泰勒级数告诉我们答案是 $\dfrac{\alpha(\alpha-1) \cdots (\alpha-k+1)}{k!}$，这个数记为 $\dbinom{\alpha}{k}$
补充定义：当 $n$ 是正整数且 $k > n$ 时，$\dbinom{n}{k} = 0$。那么，对于任何 $\alpha \in \mathbb{R}$，有 $(x+1)^\alpha = \displaystyle\sum_{k=0}^{\infty}\dbinom{\alpha}{k}x^k$

组合数恒等式

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

$\dbinom{n}{k}\dbinom{k}{m} = \dbinom{n}{m}\dbinom{n-m}{k-m}$

简单证明一下第二个恒等式：

$\begin{align} \dbinom{n}{k}\dbinom{k}{m} &= \dfrac{n!}{k!(n-k)!} \dfrac{k!}{m!(k-m)!}\\\ &= \dfrac{n!}{m!(n-m)!} \dfrac{(n-m)!}{(n-k)!(k-m)!}\\\ &= \dbinom{n}{m}\dbinom{n-m}{k-m} \end{align}$

二项式反演

$f(n) = \displaystyle\sum_{i=0}^n \dbinom{n}{i} g(i) \Leftrightarrow g(n) = \sum_{i=0}^n (-1)^{n-i}\dbinom{n}{i} f(i)$

证明：

（这里仅证明必要条件）

$\begin{align} &\displaystyle\sum_{i=0}^n (-1)^{n-i}\dbinom{n}{i} \sum_{j=0}^i \dbinom{i}{j} g(j)\\\ =& \sum_{j = 0}^n\sum_{i=j}^n (-1)^{n-i}\dbinom{n}{i} \dbinom{i}{j} g(j)\\\ =& \sum_{j = 0}^n\sum_{i=j}^n (-1)^{n-i} \dbinom{n}{j}\dbinom{n-j}{i-j} g(j)\\\ =& \sum_{j = 0}^n \dbinom{n}{j}g(j) \sum_{i=j}^n (-1)^{n-i} \dbinom{n-j}{i-j}\\\ =& \sum_{j = 0}^n \dbinom{n}{j}g(j) \sum_{i=0}^{n-j} (-1)^{n-j-i} \dbinom{n-j}{i}\\\ =& \sum_{j = 0}^n \dbinom{n}{j}g(j)[n = j] = g(n) \end{align}$