\chapter{二项式定理与贾宪三角}
\section{二项式定理}
\begin{theorem}[二项式定理]
    在$(x+y)^n$的展开式中，$x^{n-k}y^k$的系数是$\binom{n}{k}$。
    \[(x+y)^n = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^2 + \dots + \binom{n}{n-1}xy^{n-1} + \dbinom{n}{n}y^n \eqper\]
\end{theorem} 

\begin{corollary}
    令$x=y=1$，可以得到
    \[2^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n} \text{；}\]
    令$x = -y = 1$，可以得到
    \[0 = \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \dots + (-1)^n\binom{n}{n}\eqper\]
\end{corollary}

\section{k项式定理}
将$n$个礼物分给$k$个孩子，其中第一个拿到$n_1$个，第二个拿到$n_2$个，……第$n$个拿到$n_k$个。共有多少种分礼物的方式？
\begin{proof}[解]
    由题，有
    \[n_1 + n_2 + \dots + n_k = n\]
    分礼物的过程可以是：把$n$个礼物先按照某个顺序排成一排（共$n!$种排法），然后从某一端开始前$n_1$个给第一个孩子，之后的$n_2$个给第二个孩子……最后的$n_k$个分给第$k$个孩子。但是要注意到，每个孩子拿到的礼物中的内部的顺序是不重要的，因此还需要再除以$n_1!n_2!\dots n_k!$。

    综上，可能的分礼物的方法数为
    \[\frac{n!}{n_1!n_2!\dots n_k!}\eqper\qedhere\]
\end{proof}

\begin{corollary*}
    \[\sum_{n_1 + n_2 + \dots + n_k = n} \frac{n!}{n_1!n_2!\dots n_k!} = k^n \eqper\]
\end{corollary*}

\begin{proof}
    上式的意义即计算将$n$个礼物分给$k$个孩子，不限制每个孩子所得的礼物数的总方法数，即$k^n$。
\end{proof}

\begin{theorem}[k项式定理]
    \[\left(\sum_{i=1}^k x_i\right)^n = n!\sum_{n_1 + n_2 + \dots + n_k = n} \prod_{i=1}^k \frac{x_i^{n_i}}{n!} \eqper\]
\end{theorem}

\section{允许重复的组合}
\begin{example}
    将$n$个相同的硬币分给$k$个人，每人至少一个。有多少种分法？
\end{example}

\begin{theorem}\label{undistinguishable combination}
    $n$个相同物品分给$k$个人，每人至少一个，共有$\binom{n-1}{k-1}$种分法。
\end{theorem}

\begin{proof}
    将硬币排成一排，在其中选$k-1$个位置作为分隔点，就能得到一个符合要求的分法，共有$\binom{n-1}{k-1}$种。
\end{proof}

\begin{theorem}
    $n$个相同物品分给$k$个人，允许有人没有，共有$\binom{n+k-1}{k-1}$种分法。
\end{theorem}

\begin{proof}
    先在$n$个硬币中再添加$k$个，之后按照定理\ref{undistinguishable combination}中的分法再分，这样每个人至少有一个物品，再将多出的物品从每人那里拿走一个，即$\binom{n+k-1}{k-1}$种分法。
\end{proof}

上面两个定理都是允许重复的组合。它也可以写成：
\begin{enumerate}
    \item 在$k$个不同的元素中取$n$个进行组合，且允许重复，则组合数为$\binom{n+k-1}{n}$。
    \item 即：$n$个无区别的球放进$k$个有标志的盒子里，每盒放的球可多于一个，则共有$\binom{n+k-1}{n}$中方案。
\end{enumerate}

\begin{proof}
    只要证允许重复组合与$n+k-1$个不同的元素中取$n$个作不重复的组合一一对应，就可得证。

    假设$k$不同元素为$1, 2, \dots, k$。从中取$n$个作允许重复的组合（$a_1, a_2, \dots , a_n$）。不失一般性设$a_1 \leq a_2 \leq \dots \leq a_n$。

    这个组合自然地对应到一不重复的组合（$a_1, a_2 + 1, \dots a_i + i - 1, \dots, a_n + n - 1$）。

    注意到这相当于从$n+k-1$个不同的元素中取$n$个不重复的组合，故为$\binom{n+k-1}{n}$。
\end{proof}

\section{贾宪三角}
\begin{table}[H]
    \begin{center}
        \begin{tabular}{ccccccccccccc}
            & & & & & & $\dbinom{0}{0}$ & & & & & & \\
            & & & & & $\dbinom{1}{0}$ & & $\dbinom{1}{1}$ & & & & & \\
            & & & & $\dbinom{2}{0}$ & & $\dbinom{2}{1}$ & & $\dbinom{2}{2}$ & & & & \\
            & & & $\dbinom{3}{0}$ & & $\dbinom{3}{1}$ & & $\dbinom{3}{2}$ & & $\dbinom{3}{3}$ & & & \\
            & & $\dbinom{4}{0}$ & & $\dbinom{4}{1}$ & & $\dbinom{4}{2}$ & & $\dbinom{4}{3}$ & & $\dbinom{4}{4}$ & & \\
            & $\dbinom{5}{0}$ & & $\dbinom{5}{1}$ & & $\dbinom{5}{2}$ & & $\dbinom{5}{3}$ & & $\dbinom{5}{4}$ & & $\dbinom{5}{5}$ & \\
            $\dbinom{6}{0}$ & & $\dbinom{6}{1}$ & & $\dbinom{6}{2}$ & & $\dbinom{6}{3}$ & & $\dbinom{6}{4}$ & & $\dbinom{6}{5}$ & & $\dbinom{6}{6}$\\
        \end{tabular}
    \end{center}
\end{table}

\begin{table}[H]
    \begin{center}
        \begin{tabular}{ccccccccccccc}
            & & & & & & 1 & & & & & & \\
            & & & & & 1 & & 1 & & & & & \\
            & & & & 1 & & 2 & & 1 & & & & \\
            & & & 1 & & 3 & & 3 & & 1 & & & \\
            & & 1 & & 4 & & 6 & & 4 & & 1 & & \\
            & 1 & & 5 & & 10 & & 10 & & 5 & & 1 & \\
            1 & & 6 & & 15 & & 20 & & 15 & & 6 & & 1\\
        \end{tabular}
    \end{center}
\end{table}

\section{贾宪三角等式}
\begin{enumerate}
    \item $\dbinom{n}{k} = \dbinom{n}{n-k}$；
    \item $\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$；
    \item $\dbinom{n}{0} + \dbinom{n}{1} + \dots + \dbinom{n}{n} = 2^n$；
    \item $\dbinom{n}{0} - \dbinom{n}{1} + \dbinom{n}{2} - \dots + (-1)^n \dbinom{n}{n} = 0$；
    \item $\dbinom{n+m}{k} = \dbinom{n}{0}\dbinom{m}{k} + \dbinom{n}{1}\dbinom{m}{k-1} + \dots + \dbinom{n}{k}\dbinom{m}{0}, k \leq \min (m,n)$；
    \item $\dbinom{m+n}{m} = \dbinom{m}{0} \dbinom{n}{0} + \dbinom{m}{1} \dbinom{n}{1} + \dots + \dbinom{m}{m} \dbinom{n}{m}, m \leq n$；
    \item $\dbinom{n+k+1}{k} = \dbinom{n+k}{k} + \dbinom{n+k-1}{k-1} + \dbinom{n+k-2}{k-2} + \dots + \dbinom{n+1}{1} + \dbinom{n}{0}$；
    \item $\dbinom{n}{k}\dbinom{k}{r} = \dbinom{n}{r}\dbinom{n-r}{k-r}, k \geq r$。
\end{enumerate}

\section{鸟瞰贾宪三角}
贾宪三角中的每一行都是从1开始单调增加到中点，然后单调减少到一。

问题：贾宪三角的第$n$行的最大值多大？

粗略地估计，有
\[\dfrac{2^n}{n+1} < \dbinom{n}{n/2} < 2^n\eqper\]

更精确地估计，有
\[\binom{n}{n/2} = \frac{n!}{(\frac{n}{2})!(\frac{n}{2})!}\eqco\]
应用Stirling公式，
\[n! \sim \sqrt{2 \pi n} (\frac{n}{e})^n, \left(\frac{n}{2}\right)! \sim \sqrt{\pi n}\left(\frac{n}{2e}\right)^{\frac{n}{2}}\]
因此
\[\binom{n}{n/2} \sim \frac{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}{\pi n \left(\frac{n}{2e}\right)^n} = \sqrt{\frac{2}{\pi n}}2^n \eqper\]

\section{鹰瞰贾宪三角}
粗略地估计，有
\[\binom{2n}{n-t} \bigg/ \binom{2n}{n} \approx \underset{\text{高斯曲线}}{e^{-\frac{t^2}{n}}} \eqper\]

如果需要更精细的、严格的边界，有
\[e^{-\frac{t^2}{n-t+1}} \leq \binom{2n}{n-t} \bigg/ \binom{2n}{n} \leq e^{-\frac{t^2}{n+t}}\eqper\]

不等式右侧的证明：将组合数展开后取对数，再利用$\ln x \leq x - 1$放缩即可得证。

\begin{lemma}\label{lemma for Bernolli's law of large numbers}
    令$0 \leq k \leq n$且$c = \binom{2n}{k} \bigg/ \binom{2n}{n}$（即$k-1$项的高度与中心高度的比值），那么
    \[
        \underbrace{\binom{2n}{0} + \binom{2n}{1} + \dots + \binom{2n}{k-1}}_{\text{高斯曲线中从$-\infty$到$k-1$的面积}} < c \times \underbrace{2^{2n-1}}_{\text{曲线左半部分的面积}}
    \]
\end{lemma}

\begin{proof}
    注意到
    \[
        \binom{2n}{k} = c \binom{2n}{n}
    \]
    从而
    \[
        \binom{2n}{k-1} < c \binom{2n}{n-1}
    \]
    那么有
    \[
        \binom{2n}{k-i} < c \binom{2n}{n-1}
    \]
    将所有式子累加得到
    \[
        \binom{2n}{0} + \binom{2n}{1} + \dots + \binom{2n}{k-1} < c 2^{2n-1}\eqper \qedhere
    \]
\end{proof}