S_n = \begin{cases}
1 & n = 0 \\
\sum\limits_{i = 0}^{n - 1}{C_i \cdot C_{n - i - 1}} & n \geq 1
\end{cases}
下面借助这个问题解释一下这个递推式：
当 n = 0 时，C_0 = 1，因为此时终点和起点重合，我们只有不动这一种操作。
当 n \geq 1 时，我们枚举第一次碰到 y = x 的位置，设为 i，在这个位置之前是没有碰到过 y = x 这条直线，那么我们就能得到这条路径是没有越过 y = x + 1，我们就把前面的路径的方案数转化成了 C_{i - 1}，由于之后的方案数是 C_{n - i}，我们求和就得到了当前的方案数。
\begin{pmatrix} n \\ m \end{pmatrix} = \begin{pmatrix} n \\ n-m \end{pmatrix}
组合意义证明：
在 n 个物品中选出 m 个物品的方案数等于在 n 个物品中选出 n - m 个物品扔掉的方案数。
数学证明：
\begin{pmatrix} n \\ m \end{pmatrix} = \frac{n!}{m!(n - m)!} \\
\begin{pmatrix} n \\ n - m \end{pmatrix} = \frac{n!}{(n - m)![n - (n - m)]!} = \frac{n!}{m!(n - m)!}
\begin{pmatrix} n \\ m \end{pmatrix} = \frac{n}{m} \begin{pmatrix} n - 1 \\ m - 1 \end{pmatrix} = \frac{n}{n - m} \begin{pmatrix} n - 1 \\ m \end{pmatrix} = \frac{n - m + 1}{m} \begin{pmatrix} n \\ m - 1 \end{pmatrix}
组合意义证明：
考虑从 n 个物品中选择 m 个的方案数，等同于先选择一个物品，有 n 中方案，再在剩下的 n - 1 个物品中选择 m - 1 个，但是其实先选的这个物品可以在这 m 个中的任意一个，于是除以 m 得到正解。
第三个式子其实就是上面的式子中把选 m 个变成选 n - m 个去掉即可。
最后一个可以认为是在 n 个物品中选了 m - 1 个，再在剩下的 n - m + 1 个中选最后一个，但也是可以出现在任意一个位置，所以再除以 m。
数学证明：
\begin{align*}
&\begin{pmatrix} n \\ m \end{pmatrix} = \frac{n!}{m!(n - m)!} \\
&\frac{n}{m} \begin{pmatrix} n - 1 \\ m - 1 \end{pmatrix} = \frac{n (n - 1)!}{m (m - 1)!(n - m)!} = \frac{n!}{m!(n - m)!} \\
&\frac{n}{n - m} \begin{pmatrix} n - 1 \\ m \end{pmatrix} = \frac{n (n - 1)!}{(n - m) m!(n - 1 - m)!} = \frac{n!}{m!(n - m)!} \\
&\frac{n - m + 1}{m} \begin{pmatrix} n \\ m - 1 \end{pmatrix} = \frac{(n - m + 1) n!}{m(m - 1)!(n - m + 1)!} = \frac{n!}{m!(n - m)!}
\end{align*}
\begin{pmatrix} n \\ m \end{pmatrix} = \begin{pmatrix} n - 1 \\ m \end{pmatrix} + \begin{pmatrix} n - 1 \\ m - 1 \end{pmatrix}
组合数最出名的递推式。
组合意义证明：
考虑选或不选第 m 个数，如果选的话，那么我们就需要从前 n - 1 个数中选 m - 1 个数，如果不选，那么我们就需要在前 n - 1 个数中选 m 个数，根据加法原理，我们就能得到这个恒等式。
数学证明：
\begin{align*}
&\begin{pmatrix} n - 1 \\ m \end{pmatrix} + \begin{pmatrix} n - 1 \\ m - 1 \end{pmatrix} \\
&= \frac{(n - 1)!}{m!(n - 1 - m)!} + \frac{(n - 1)!}{(m - 1)!(n - m)!} \\
&= \frac{(n - 1)!(n - m)}{m!(n - m)!} + \frac{(n - 1)!m}{m!(n - m)!} \\
&= \frac{(n - 1)!(n - m + m)}{m!(n - m)!} \\
&= \frac{n!}{m!(n - m)!} \\
&= \begin{pmatrix} n \\ m \end{pmatrix}
\end{align*}
\begin{pmatrix} n \\ m \end{pmatrix} \begin{pmatrix} m \\ k \end{pmatrix} = \begin{pmatrix} n \\ k \end{pmatrix} \begin{pmatrix} n - k \\ m - k \end{pmatrix}
组合意义证明：
根据乘法原理，考虑将等式左边理解为先从 n 个物品中选择 m 个，再从选出的 m 个物品中选择 k 个。
考虑等价选法，先从 n 个物品中选择 k 个，再从剩下的 n - k 个物品中选择剩余的 m - k 个，则原先选择的 m 个物品可由选出的 k 个物品和 m - k 个物品合并得来。
转化后的选法即为等式右边。
数学证明：
\begin{align*}
&\begin{pmatrix} n \\ m \end{pmatrix} \begin{pmatrix} m \\ k \end{pmatrix}\\
&= \frac{n!}{m!(n - m)!} \cdot \frac{m!}{k!(m - k)!} \\
&= \frac{n!}{(n - m)!k!(m - k)!} \\
&\begin{pmatrix} n \\ k \end{pmatrix} \begin{pmatrix} n - k \\ m - k \end{pmatrix} \\
&= \frac{n!}{k!(n - k)!} \cdot \frac{(n - k)!}{(m - k)!(n - m)!} \\
&= \frac{n!}{k!(m - k)!(n - m)!}
\end{align*}
(x + y)^n = \sum\limits_{k = 0}^{n}{\begin{pmatrix} n \\ k \end{pmatrix} x^k y^{n - k}}
组合意义证明：
考虑对于每个 k，在这一项中我们在全部 n 个式子中选择了共 k 个 x，总方案数为 \begin{pmatrix} n \\ k \end{pmatrix}，对应着这一项的系数，我们就得到了这个式子。
数学证明：
考虑递推思想解决。
根据式子，在 n - 1 个数中选 k 个 x 的方案数为 \begin{pmatrix} n - 1 \\ k \end{pmatrix}，在 n - 1 个数中选 k - 1 个 x 的方案数为 \begin{pmatrix} n - 1 \\ k - 1 \end{pmatrix}。考虑这一个位置选 x 或 y，总方案数正好对应着上面两个式子的和，根据上面介绍过的递推式我们可以得到在 n 个数中选 k 个 x 的方案数为 \begin{pmatrix} n \\ k \end{pmatrix}。
\sum\limits_{k}{\begin{pmatrix} n \\ k \end{pmatrix} k^{\underline{m}} x^{k - m}} = n^{\underline{m}} (1 + x)^{n - m}
组合意义证明：
等式右边可以理解为这里有 n 个人，我们先选出 m 个人排成一列，剩下每个人在 x + 1 个职业中选择一个的方案数。那么等式左边可以先转化为 \sum\limits_{k}{\begin{pmatrix} n \\ k \end{pmatrix} k^{\underline{m}} x^{k - m}}，然后我们可以尝试理解，枚举一个 k，先在 n 个人中选出 k 个人去选 x 个职业，在选出 m 个人去排队，剩下的人选第 x + 1 个职业。
数学证明：
考虑去掉 k^{\underline{m}} 这一项，很明显这是一个二项式定理，那么此式就是二项式定理式子对 x 求 m 介导后的式子。
\sum\limits_{k \le n}{\begin{pmatrix} k \\ m \end{pmatrix}} = \begin{pmatrix} n + 1 \\ m + 1 \end{pmatrix}
组合意义证明：
考虑在 n + 1 个物品中选择 m + 1 个物品的方案数，我们先枚举在前 k 个物品中选择 m 个，第 k + 1 个到第 n 个都不选，再选上后面剩余的一个的方案数。
数学证明：
根据递推式，我们可以把右边的式子化为 \sum\limits_{k = 0}^{n}{\begin{pmatrix} k \\ m \end{pmatrix}} + \begin{pmatrix} 0 \\ m + 1 \end{pmatrix}，由于有 0 < m + 1，所以最后一项为 0，去掉最后一项后我们就得到了等式左边的式子。
\sum\limits_{i = 0}^{k}{\begin{pmatrix} n \\ i \end{pmatrix} \begin{pmatrix} m \\ k - i \end{pmatrix}} = \begin{pmatrix} n + m \\ k \end{pmatrix}
大名鼎鼎的范德蒙德卷积。在介绍完普通的范德蒙德卷积之后，我还会在这一块介绍一下范德蒙德卷积的四个推论。
组合意义证明：
等式右边的意义为在 n + m 个物品中选 k 个的方案数。我们考虑把这 n + m 个物品拆分成两部分，先从前 n 个物品中选一些，再从后 m 个方案中选出剩下的，枚举一个 i 即可。
数学证明：
考虑使用二项式定理证明。
\begin{align*}
&\sum\limits_{k = 0}^{n + m}{\begin{pmatrix} n + m \\ k \end{pmatrix} x^k} \\
&= (x + 1)^{n + m} \\
&= (x + 1)^n (x + 1)^m \\
&= \sum\limits_{i = 0}^{n}{\begin{pmatrix} n \\ i \end{pmatrix} x^i} \sum\limits_{j = 0}^{m}{\begin{pmatrix} m \\ j \end{pmatrix} x^j} \\
&= \sum\limits_{k = 0}^{n + m}{\sum\limits_{i = 0}^{k}{\begin{pmatrix} n \\ k \end{pmatrix} \begin{pmatrix} m \\ k - i \end{pmatrix} x^k}}
\end{align*}
去掉最外层的枚举 k 和右边的 x^k，我们就得到了范德蒙德卷积的式子。
推论式1
\sum\limits_{i = -r}^{s}{\begin{pmatrix} n \\ r + i \end{pmatrix} \begin{pmatrix} m \\ s - i \end{pmatrix}} = \begin{pmatrix} n + m \\ r + s \end{pmatrix}
考虑更换范德蒙德卷积所枚举的变量即可。
推论式2
\sum\limits_{i = 1}^{n}{\begin{pmatrix} n \\ i \end{pmatrix} \begin{pmatrix} n \\ i - 1 \end{pmatrix}} = \begin{pmatrix} 2n \\ n - 1 \end{pmatrix}
考虑更换枚举变量和其中一个等价式即可得到范德蒙德卷积的形式。
推论式3
\sum\limits_{i = 0}^{n}{\begin{pmatrix} n \\ i \end{pmatrix}^2} = \begin{pmatrix} 2n \\ n \end{pmatrix}
考虑更换等价式即可得到范德蒙德卷积的形式。
推论式4
\sum\limits_{i = 0}^{m}{\begin{pmatrix} n \\ i \end{pmatrix} \begin{pmatrix} m \\ i \end{pmatrix}} = \begin{pmatrix} n + m \\ m \end{pmatrix}