排列与组合
排列：从$n$个不同元素中取出$m$ ($m \leq n$) 个元素，按照一定的次序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列。
排列数：排列：从$n$个不同元素中取出$m$ ($m \leq n$) 个元素，按照一定的次序排成一列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，记作 $P_n^m$。
$$
P_n^m = \frac {n!} {(n-m)!}
$$
排列：从$n$个不同元素中取出$m$ ($m \leq n$) 个元素组成一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合。
排列数：排列：从$n$个不同元素中取出$m$ ($m \leq n$) 个元素的组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，记作 $C_n^m$。
$$
C_n^m = \frac {n!} {(n-m)!m!}
$$
用排列理解组合
组合的本质是无序的排列。对于每一种含有 $m$ 个元素组合，能够产生 $m!$ 个排列，所以：
$$
C_n^m = \frac {P_n^m} {m!}
$$
组合数的性质
$$
C_n^m = C_n^{n-m}
$$
证明：
- 从定义出发：在$n$个东西中选出$m$个东西，和在$n$个东西中选出$n-m$个不选的东西等价
- 从表达式出发：
$$
C_n^{n-m} = \frac {n!} {(n-m)!(n-n+m)!} = \frac {n!} {m!(n-m)!} = C_n^m
$$
帕斯卡法则
$$
C_n^k + C_n^{k+1} = C_{n+1}^{k+1}
$$
证明：
- 代数证明：
$$
\begin{aligned}
C_n^k + C_n^{k+1} &= \frac {n!} {k!(n-k)!} + \frac {n!} {(k+1)!(n-k-1)!} \\
&= \frac {n!} {k!(n-k)!} + \frac {n!(n-k)} {(k+1)k!(n-k)!} \\
&= \frac {n!} {k!(n-k)!} (1 + \frac {n-k} {k+1}) \\
&= \frac {n!} {k!(n-k)!} \frac {n + 1} {k + 1} = \frac {(n+1)!} {(n-k-1)!} \\
&= C_{n+1}^{k+1}
\end{aligned}
$$ - 从定义出发：在$n+1$个东西中取出$k+1$个东西，可以分为两种情况。我们任取一个东西把他视为「特殊物品」，那么在$n+1$中取$k+1$个东西变能够变成：
- 不取「特殊物品」，在剩下$n$个物品中取$k+1$个，$C_n^{k+1}$
- 取「特殊物品」，在剩下$n$个物品中取$k$个，$C_n^k$
帕斯卡法则的推论
$$
\sum_{i = 0}^k C_{n+i}^n = C_n^n + C_{n+1}^n + C_{n+2}^n + \cdots + C_{n+k}^n = C_{n+k+1}^{n+1}
$$
证明：
方法一：
能够注意到：
$$
C_n^n + C_{n+1}^n = C_{n+1}^{n+1} + C_{n+1}^n = C_{n+2}^{n+1}
$$
则：
$$
\begin{aligned}
&C_n^n + C_{n+1}^n + C_{n+2}^n + \cdots + C_{n+k}^n \\
=&C_{n+2}^{n+1} + C_{n+2}^n + \cdots + C_{n+k}^n \\
=&C_{n+3}^{n+1} + C_{n+3}^n + \cdots + C_{n+k}^n \\
&\cdots \\
=&C_{n+k+1}^{n+1}
\end{aligned}
$$
方法二：
数学归纳法的递推关系：
若
$$
\sum_{i = 0}^k C_{n+i}^n = C_n^n + C_{n+1}^n + C_{n+2}^n + \cdots + C_{n+k}^n = C_{n+k+1}^{n+1}
$$
成立，则：
$$
\sum_{i = 0}^{k+1} C_{n+i}^n = C_n^n + C_{n+1}^n + C_{n+1}^n + \cdots + C_{n+k+1}^n = C_{n+k+1}^{n+1} + C_{n+k+1}^n = C_{n+k+2}^{n+1}
$$
用帕斯卡法则的推论构造一系列求和公式
$$
\sum_{i=1}^n i = C_1^1 + C_2^1 + \cdots + C_n^1 = C_{n+1}^2 = \frac {n(n+1)} 2
$$
$$
\sum_{i=1}^n i(i+1) = 2! (C_2^2 + C_3^2 + \cdots + C_{n+1}^2) = 2! C_{n+2}^3
$$
$$
\sum_{i=1}^n i(i+1)(i+2) = 3! (C_3^3 + C_4^3 + \cdots + C_{n+2}^3) = 3! C_{n+3}^4
$$
$$
\sum_{i=1}^n i^2 = \sum_{i=1}^n [i(i+1) - i] = \sum_{i=1}^n i(i+1) - \sum_{i=1}^n i
$$
$$
\sum_{i=1}^n i^3 = \sum_{i=1}^n [i(i+1)(i+2) - 3i^2 - 2i]
$$
其他结论
$$
iC_n^i = nC_{n-1}^{i-1}
$$
证明：
$$
LHS = i \frac {n!} {i!(n-i)!} = \frac {n!}{(i-1)!(n-i)!}
$$
$$
RHS = n \frac {(n-1)!}{(i-1)!(n-i)!} = \frac {n!}{(i-1)!(n-i)!}
$$
$$
LHS = RHS
$$
二项式定理
$$
(a+b)^n = C_n^0 a^n + C_n^1 a^{(n-1)}b + \cdots + C_n^n b^n = \sum_{i=0}^n C_{n}^i a^{n-i}b^i
$$
二项式定理的推论
$$
(1+x)^n = C_n^0 + C_n^1 x + \cdots + C_n^n x^n = \sum_{i=0}^n C_{n}^i x^i
$$
$$
(1+1)^n = C_n^0 + C_n^1 + \cdots + C_n^n = \sum_{i=0}^n C_{n}^i = 2^n
$$
$$
(1-1)^{2n} = C_{2n}^0 - C_{2n}^1 + \cdots + C_{2n}^2n = 0
$$
$$
(1-1)^{2n+1} = C_{2n+1}^0 - C_{2n+1}^1 + \cdots - C_{2n+1}^{2n+1} = 0
$$
$$
(1+i)^{n} = C_n^0 + C_n^1 i + C_n^2 i^2 + \cdots + C_n^n i^n
$$
多项式定理
不定方程组的正整数解
题目
$m$ 个苹果分给 $n$ 个小孩，每个小孩至少拿一个苹果，问有多少种分法。
问题抽象
第 $i$ 个小孩拿到 $y_i$ 个苹果：
$$
\begin{cases}
\sum_i y_i = m \\
y_i > 0 \\
m, y_i \in \mathbb Z
\end{cases}
$$
方法：插板法
$$
\bigcirc ~ \bigcirc ~ \bigcirc ~ \cdots ~ \bigcirc ~ \bigcirc ~ \bigcirc
$$
$m$ 个苹果拍成一排，中间有 $m-1$ 个空，插 $n - 1$ 个板子，故方法数为 $C_{m-1}^{n-1}$
不定方程组的非负整数解
题目
$m$ 个苹果分给 $n$ 个小孩，小孩也可以不拿苹果，问有多少种分法。
问题抽象
第 $i$ 个小孩拿到 $y_i$ 个苹果：
$$
\begin{cases}
\sum_i y_i = m \\
y_i \geq 0 \\
m, y_i \in \mathbb Z
\end{cases}
$$
解法
（一）转化为插板法
$$
\begin{cases}
\sum_i (y_i + 1) = m + n \\
(y_i + 1) \geq 1 \\
m, y_i + 1 \in \mathbb Z
\end{cases}
$$
方法数即为：$C_{m+n-1}^{n-1}$
（二）暴力枚举
如果有 $i$ 个小孩能分到苹果，剩下的小孩分不到苹果，那么这个时候的方法数即为：
$$
(从 n 个小孩种选出 i 个小孩的组合数) \times (m 个苹果分给 i 个小孩的方案数)
$$
即为
$$
C_n^i C_{m-1}^{i-1}
$$
所以总方案数即为
$$
\sum_{i = 1}^n C_n^i C_{m-1}^{i-1}
$$
（三）思考
上面的两种情况都是对的，我们得到一个恒等式：
$$
\sum_{i = 1}^n C_n^i C_{m-1}^{i-1} = C_{m+n-1}^{n-1}
$$
多项式定理
$$
\Big( \sum_{i=1}^n x_i \Big) ^ m = \sum_{\sum_i m_i = m,~m_i \geq 0} \frac {m!} {\prod_i m_i !} \prod_{i=1}^n x_i^{m_i}
$$
总共有 $C_{n+m-1}^{n-1}$ 项。读者自证不难，需要推广一下组合数。
