二项式系数 Binomial Coefficients
1.1 基本恒等式 Basic Identities
1.1.1 定义 Definition
\binom nk 表示二项式系数，其中 n 称作上指标 (upper index)，而称 k 为下指标 (lower index)。
1.1.2 对称恒等式 Symmetric Identity
证明：
\binom nk=\frac{n!}{k!(n-k)!}=\frac{n!}{(n-(n-k))!(n-k)!}=\binom n{n-k}1.1.3 吸收恒等式 Absorption Identity
\binom rk=\frac rk\binom {r-1}{k-1}证明：
- k> 0
- k<0
\binom rk = 0 = \binom {r-1}{k-1}1.1.3+ 相伴恒等式 Companion Identity
(r-k)\binom rk=r\binom {r-1}k证明：
\begin{aligned}(r-k)\binom rk & =(r-k)\binom r {r-k}\\& = r\binom {r-1}{r-k-1}\\& = r\binom {r-1}k\end{aligned}1.1.4 加法公式 Addition Formula
\binom rk = \binom {r-1}k+\binom {r-1}{k-1}证明：
r\binom rk=(r-k)\binom rk +k\binom rk=r\binom {r-1}k+r\binom {r-1}{k-1}1.1.5 上指标求和 Summation of Upper Indicators
证明：
利用数学归纳法。
n=0 时，左边 =\binom 0m=[m=0]=\binom 1{m+1}= 右边
时，
\begin{aligned}\sum_{0\leq k\leq n+1}\binom km & =\sum_{0\leq k\leq n}\binom km+\binom {n+1}m\\& = \binom {n+1}{m+1} +\binom {n+1}m\\& = \binom {n+2}{m+1}\end{aligned}所以对一切
，(1) 成立。
1.1.6 平行求和法 Parallel Summation
证明：
\begin{aligned}\sum_{k\leq n}\binom {m+k}k & =\sum_{-m\leq k\leq n}\binom {m+k}k\\& = \sum_{-m\leq k\leq n}\binom {m+k}m\\& = \sum_{0\leq k\leq m+n}\binom km\\& = \binom {m+n+1}{m+1}\end{aligned}注意到以上证明当且仅当 m+k\ge 0 才可以这么做（第二行运用到对称法则），因此我们在第一步去掉了 k<-m
1.1.7 上指标反转 Upper Negation
证明：
- k\ge 0
$\binom rk=\frac{r^{\underline k}}{k!}=\frac{(-1)^k (-r)(1-r)\cdots (k-1-r)}{k!}=\frac {(-1)^k(k-r-1)^{\underline k}}{k!}=(-1)^k\binom {k-r-1}k- k<0
\binom rk = 0 = (-1)^k\binom {k-r-1}k1.1.8 三项式版恒等式 Trinomial Version of Identity
证明：
，
\begin{aligned}\binom rm\binom mk & = \frac{r!}{m!(r-m)!}\frac{m!}{k!(m-k)!} \\& = \frac{r!}{k!(m-k)!(r-m)!}\\& = \frac{r!}{k!(r-k)!}\frac{(r-k)!}{(m-k)!(r-m)!}\\& = \binom rk \binom {r-k}{m-k}\end{aligned}若 m<kk<00。
1.1.9 范德蒙德卷积 Vandermonde Convolution
证明：
这里可以暂时通过组合意义来简单证明：
先从 r 个球中取 m+k 个，再从 s 个球中取 n-k 个，就相当于在 r+s 个球中取 m+n 个。
具体严谨证明见下文——生成函数。
1.1.10 二项式定理 Binomial Theorem
(x+y)^n=\sum_{k=0}^n\binom nky^kx^{n-k}\quad n\in Z_+特别地，
(1+x)^n=\sum_{k=0}^n\binom nkx^k\quad n\in Z_+1.1.11 其他基本组合恒等式 Other Basic Combination Identities
\sum_{k=0}^n \binom nk=2^n \tag 1\sum_{k=0}^n (-1)^k\binom nk=0 \tag 21.2 生成函数 Generating Function
1.2.1 卷积 Convolution
c_n=\sum_{k=0}^na_kb_{n-k} \tag1由 (1) 所定义的序列 \langle c_n\rangle 称为序列 \langle a_n\rangle 和 \langle b_n \rangle 的卷积。
1.2.2 二项式定理与生成函数 Binomial Theorem and Generating Function
(1+z)^r=\sum_{k\ge 0}\binom rkz^k \tag1类似地，
(1+z)^s=\sum_{k\ge 0}\binom skz^k \tag2将 (1)(2) 相乘，我们可以得到另外一个生成函数：
(1+z)^r(1+z)^s=(1+z)^{r+s}让这个等式两边 z^n 的系数相等就给出：
\sum_{k=0}^n\binom rk\binom s{n-k}=\binom {r+s}n我们就发现了范德蒙德卷积。
此外我们还有一系列重要的恒等式：
(1-z)^r=\sum_{k\ge 0}(-1)^k\binom rk\tag 3当 n=0 时，我们就得到了 (4) 的特例，即几何级数：
\frac 1{1-z}=1+z+z^2+z^3+\cdots =\sum_{k\ge 0}z^k这就是序列 \langle 1,1,1,\cdots \rangle 的生成函数。
1.3 基本练习 Basic Practice
1.3.1 利用基本组合恒等式 Use Basic Combinatorial Identities
- 证明：\sum_{k=1}^n (-1)^{k-1}k\binom nk=0 \ (n\ge2)
\begin{aligned}LHS & = \sum_{k=1}^n(-1)^{k-1}n\binom {n-1}{k-1} \\& = n\sum_{k}(-1)^k\binom nk\\& = n\binom 0n\\& = n[n=0]\\& = 0 = RHS\end{aligned}- 证明：\sum_{k=p}^n\binom nk\binom kp=\binom np2^{n-p}
\begin{aligned}LHS & = \sum_{k=p}^n\binom np\binom {n-k}{k-p}\\& = \binom np\sum_{k=0}^{n-p}\binom {n-p-k}k\\& = \binom np 2^{n-p} = RHS\end{aligned}1.3.2 利用生成函数 Use Generating Functions
- 证明：
- \sum_{k=0}^n{\binom nk}^2=\binom n{2n}
- \sum_{k=1}^{2n-1}\binom {2n}k[2 (k-1)]=\frac 12{\binom {4n}{2n}+(-1)^{n-1}\binom {2n}n}
[collapse title=”解答”] 1. 首先有：
\begin{aligned} [z^n](1+z)^{2n} & =\sum_{k=0}^{2n}\binom {2n}kz^k\\ & =\binom {2n}n \end{aligned} \begin{aligned} [z^n](1+z)^{2n} & =[z^n]((1+z)^n)^2\\ & = [z^n](\sum_{i=0}^n\binom niz^i)\cdot (\sum_{j=0}n\binom njz^j)\\ & =\sum_{k=0}^n\binom nk\binom n{n-k}\\ & =\sum_{k=0}^n{\binom nk}^2 \end{aligned} \sum_{k=0}^n{\binom nk}^2=\binom {2n}n 2. 由小题 得：
\sum_{k=0}^{2n}\binom {2n}k^2=\binom {4n}{2n}\tag1 其次：
\begin{aligned} [z^{2n}](1-z^2)^{2n} & =[z^{2n}]\sum_{k=0}^{2n}(-1)^k\binom {2n}kz^{2k}\\ & =(-1)^n\binom {2n}n \end{aligned} \begin{aligned} [z^{2n}](1-z^2)^{2n} & =(1-z)^{2n}(1+z)^{2n}\\ & = [z^{2n}](\sum_{k=0}^{2n}(-1)^k\binom {2n}kz^k)(\sum_{j=0}^{2n}\binom {2n}jz^j)\\ & = \sum_{k=0}^{2n}(-1)^k\binom {2n}k\binom {2n}{2n-k}\\ & = \sum_{k=0}^{2n}(-1)^k\binom {2n}k^2 \end{aligned} (-1)^n\binom {2n}n=\sum_{k=0}^{2n}(-1)^k\binom {2n}k^2 \tag 2 由 得：
\sum_{k=1}^n\binom {2n}{2k-1}^2=\frac 12\{\binom {4n}{2n}+(-1)^{n-1}\binom {2n}n\} [/collapse]
