1. 零些记号
略。咕咕咕
2. 排列与组合
\(\color{plum}\texttt{Watch you leaving}\)
\(\color{violet}\texttt{And I try to tell myself that I'm just streaming}\)
\(\color{magenta}\texttt{I'm just streaming}\)
2.1 四则计数原理
- 设集合 \(S\) 的一个划分（\(\text{partition}\)）是满足下面条件的子集 \(S_1,S_2,\cdots,S_m\) 的集合，即使得 \(S\) 的每一个元素恰好只属于这些子集中的一个子集：
所以集合 \(S_1,S_2,\cdots,S_m\) 两两不交，它们的并集是 \(S\)。子集 \(S_1,S_2,\cdots,S_m\) 成为该划分的部分（\(\text{part}\)）。
2.1.1
加法原理 设集合 \(S\) 被划分为两两不交的部分 \(S_1,S_2,\cdots,S_m\)。则 \(S\) 的对象数目可以通过确定它的每一个部分的对象数目相加得到：
\[\lvert S\rvert=\lvert S_1\rvert+\lvert S_2\rvert+\cdots+\lvert S_m\rvert \]
- 运用加法原理的技巧是把集合 \(S\) 划分成少量的易处理部分。
2.1.2
乘法原理 令 \(S\) 是对象的有序对 \((a,b)\) 的集合，其中第一个对象 \(a\) 来自大小为 \(p\) 的一个集合，而对于对象 \(a\) 的每个选择，对象 \(b\) 有 \(q\) 种选择。于是 \(S\) 的大小为 \(p\times q\)：
\[\lvert S\rvert=p\times q \]
- 乘法原理的第二种实用形式是：如果第一项任务有 \(p\) 个结果，而且不论第一项任务的结果如何，第二项任务都有 \(q\) 个结果，那么这两项任务连续执行就有 \(p\times q\) 个结果。
2.1.3
减法原理 令 \(A\) 是一个集合，而 \(U\) 是一个包含 \(A\) 的一个更大集合。设：
\[\overline{A}=U\setminus A=\left\{x\in U:x\notin A\right\} \]是 \(A\) 在 \(U\) 中的补（\(\text{complement}\)）。那么 \(A\) 中的对象数目 \(\lvert A\rvert\) 为：
\[\lvert A\rvert=\lvert U\rvert-\lvert\overline{A}\rvert \]
- 在应用减法原理时，集合 \(U\) 通常是包含讨论中所有对象的某个自然集合，即所谓的泛集（\(\text{universal \ set}\)）。只有在计数 \(A\) 中对象数目相对更容易计数 \(U\) 和 \(A\) 的对象数目时，使用减法原理才会有效。
2.1.4
除法原理 令 \(S\) 是一个有限集合，把它划分成 \(k\) 个部分使得每一部分包含的对象数目相同。于是，此划分中的部分的数目由下述公式给出：
\[k=\dfrac{\lvert S\rvert}{\text{在一个部分中的对象数目}} \]
- 因此，如果我们知道 \(S\) 中的对象数目以及各部分所含对象数目的共同值，就可以确定部分的数目。
2.2 集合的排列
- 令 \(r\) 为正整数，定义 \(n\) 元集合 \(S\) 的 \(r\) 排列为 \(n\) 个元素中的 \(r\) 个元素的有序放置。若 \(S=\{a,b,c\}\)，那么：
\(S\) 的 \(1\) 排列有：
\[a\qquad b\qquad c \]\(S\) 的 \(2\) 排列有：
\[ab\qquad ac\qquad ba\qquad bc\qquad ca\qquad cb \]\(S\) 的 \(3\) 排列有：
\[abc\qquad acb\qquad bac\qquad bca\qquad cab\qquad cba \]我们用 \(P(n,r)\) 表示 \(n\) 元集合 \(S\) 的 \(r\) 排列的数目。
2.2.1 集合的线性排列
- 对于正整数 \(n,r\)，\(r\leq n\)，我们有：
证明 在构建排列时，可以用 \(n\) 种方法选择第一项，不论第一项如何选出，都可以用 \(n-1\) 种方法选择第二项，以此类推，不论前 \(r-1\) 项如何选出，都可以用 \(n-r+1\) 种方法选出第 \(r\) 项。根据乘法原理，等式成立。\(\square\)
若我们将线性排列首尾相接，即可得到循环排列。具体地，例如循环排列 \(1,2,3\) 可以来自于 \((1,2,3)\)、\((2,3,1)\)、\((3,2,1)\) 中的任意一个。
2.2.2 集合的循环排列
- \(n\) 元集合的循环 \(r\) 排列的数目是：
特别地，\(n\) 个元素的循环排列的数目是 \((n-1)!\)。
证明 能够把线性 \(r\) 排列的集合划分成若干部分，使得两个线性 \(r\) 排列对应于同一个循环 \(r\) 排列当且仅当这两个线性 \(r\) 排列在同一部分中。因此循环 \(r\) 排列的数目就等于划分的部分的数目。由于每一个部分都含有 \(r\) 个线性 \(r\) 排列，因此等式成立。\(\square\)
2.3 集合的组合（子集）
设 \(S\) 是 \(n\) 元集合。\(S\) 的一个组合表示其元素的一个无序选择。这样一个选择的结果是 \(S\) 的元素构成的一个子集（\(\text{subset}\)），记为:
\[A\subseteq S \]- 例如 \(S=\{a,b,c,d\}\)，那么：
都是 \(S\) 的 \(3\) 子集。从组合意义上来说，我们用 \(\binom{n}{r}\) 来表示 \(n\) 元集合的 \(r\) 子集的数目。
2.3.1
- 对于 \(0\leq r \leq n\)，有：
所以有：
\[\dbinom{n}{r}=\dfrac{n!}{(n-r)!} \]证明 令 \(S\) 是一个 \(n\) 元素集合。\(S\) 的每一个排列都恰好有下面两个任务的执行结果而产生：
- 从 \(S\) 中选出 \(r\) 个元素。
- 以某种顺序摆放选出的 \(r\) 个元素。
根据定义，执行第一个任务的方法数目是 \(\binom{n}{r}\)。执行第二个任务的方法数则是 \(P(r,r)=r!\)。
根据乘法原理，我们有 \(P(n,r)=r!\binom{n}{r}\)，再套用公式即可得到式子二。\(\square\)
这玩意有几个基础的推论：
2.3.2
对于 \(0\leq r\leq n\)，有：
\[\dbinom{n}{r}=\dbinom{n}{n-r} \]证明 从 \(n\) 个任务中选择 \(r\) 个与不选择 \(n-r\) 个是等价的。\(\square\)
2.3.3 帕斯卡公式
对于 \(1\leq k<n\)，有：
\[\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1} \]证明 动态规划。\(\square\)
2.3.4
对于 \(n\geq0\)，有：
\[\dbinom{n}{0}+\dbinom{n}{1}+\cdots+\dbinom{n}{n}=2^n \]证明 我们发现 \(S\) 的每一个子集是相对于某个 \(r=0,1,2,\cdots,n\) 的 \(r\) 子集。因为 \(\binom{n}{r}\) 等于 \(S\) 的 \(r\) 子集数量，所以根据加法原理，等式成立。\(\square\)
2.4 多重集合的排列
如果 \(S\) 是一个多重集合，那么 \(S\) 的一个 \(r\) 排列是\(S\) 中 \(r\) 个对象的一个有序放置。如果 \(S\) 的总对象数是 \(N\)，那么 \(S\) 的 \(n\) 排列也称为 \(S\) 的排列。
- 例如 \(S=\{2\cdot a,1\cdot b,3\cdot c\}\)，那么 \(abcc\) 和 \(cnca\) 等都为 \(S\) 的 \(4\) 排列，\(abccac\) 为 \(S\) 的一个排列。
2.4.1
设 \(S\) 是有 \(k\) 种不同类型对象的多重集合，每一个元素都有无限重复数。那么 \(S\) 的 \(r\) 排列的数目是 \(k^r\)。
证明 在构造排列时，可以将第一项选择为 \(k\) 个类型中的任意一个，类似地，所有项都可以选择 \(k\) 个类型的一个对象。根据乘法原理， \(r\) 项共有 \(k^r\) 种选择方法。\(\square\)
2.4.2
设 \(S\) 为多重集合，有 \(k\) 种类型对象 \(a_1,a_2,\cdots,a_k\)，重复数分别为 \(n_1,n_2,\cdots,n_k\)，对象总数目为 \(n=n_1+n_2+\cdots+n_k\)。则 \(S\) 的排列数目为：
\[\dfrac{n!}{n_1!n_2!\cdots n_k!} \]证明 考虑一个个放置。\(a_1\) 的放置的方法数为 \(\binom{n}{n_1}\)。由于还剩 \(n-n_1\) 个位置，要选出 \(n_2\) 个位置来，所以 \(a_2\) 的方法数为 \(\binom{n-n_1}{n_2}\)。以此类推，不难得到：
\[\begin{aligned}&\dbinom{n}{n_1}\dbinom{n-n_1}{n_2}\cdots\dbinom{n-n_1-n_2-\cdots-n_{k-1}}{n_k}\\=&\dfrac{n!}{n_1!(n-n_1)!}\dfrac{(n-n_1)!}{n_2!(n-n_1-n_2)!}\cdots\dfrac{(n-n_1-n_2-\cdots-n_{k-1})!}{n_k!(n-n_1-n_2-\cdots-n_k)!}\\=&\dfrac{n!}{n_1!n_2!\cdots n_k!0!}=\dfrac{n!}{n_1!n_2!\cdots n_k!}\square\end{aligned} \]
2.5 多重集合的组合
如果 \(S\) 是多重集合，那么 \(S\) 的 \(r\) 组合是 \(S\) 中的 \(r\) 个对象的无序选择。因此 \(S\) 的一个 \(r\) 组合本身也是一个多重集合，它是一个大小为 \(r\) 的 \(S\) 的多重子集。
- 例如设 \(S=\{2\cdot a,1\cdot b,1\cdot c\}\)，那么 \(S\) 的 \(2\) 组合是：
2.5.1
设 \(S\) 是有 \(k\) 种类型对象的多重集合，每种元素均具有无限的重复数。那么 \(S\) 的 \(r\) 组合的个数等于：
\[\dbinom{r+k-1}{r}=\dbinom{r+k-1}{k-1} \]证明 设 \(S\) 的 \(k\) 种类型的对象是 \(a_1,a_2,\cdots,a_k\)，使得：
\[S=\{\infty\cdot a_1,\infty\cdot a_2,\cdots,\infty\cdot a_k\} \]\(S\) 的任意 \(r\) 组合均呈 \(\{x_1\cdot a_1,x_2\cdot a_2,\cdots,x_k\cdot a_k\}\) 的形式，其中 \(x_i\leq 0,\sum_x=r\)。反过来 \(S\) 的 \(r\) 组合的个数等于这个方程的解的个数。这是个典题。\(\square\)
- 这个玩意的另一种表达方式是：在每个对象的供给是无限的情况下，\(k\) 个不同对象的 \(r\) 组合数等于 \(\binom{r+k-1}{r}\)。
2.6 有限概率
有限概率相对于以微积分为基础的连续概率。
- 有一个实验 \(\mathcal{E}\)，在进行这个实验时，它产生的结果是某有限集合中的一个。
假设每一个结果都是等可能的（\(\text{equally likely}\)），这时我们说这个实验 \(\mathcal{E}\) 是随机的（\(\text{randomly}\)）。
所有可能结果的集合被称为这个实验的样本空间（\(\text{sample space}\)），并记为 \(S\)。因此，\(S\) 是一个有限集合。
例如集合：
\[S=\{s_1,s_2,\cdots,s_n\} \]当我们进行实验 \(\mathcal{E}\) 时，每一个 \(s_i\) 都有 \(1/n\) 的出现机会，所以说结果 \(s_i\) 的概率是 \(1/n\)，记为：
\[\text{Prob}(s_i)=1/n\quad(i=1,2,\cdots,n) \]一个事件（\(\text{event}\)）就是样本空间 \(S\) 的一个子集 \(E\)，通常用描述式语言给出。
在样本空间为 \(S\) 的实验中，事件 \(E\) 的概率 （\(\text{probability}\)）定义为 \(S\) 中属于 \(E\) 的结果的比率：
\[\text{Prob}(E)=\dfrac{\lvert E\rvert}{\lvert S\rvert} \]根据定义有：
\[0\leq\text{Prob}(E)\leq 1 \]其中 \(\text{Prob}(E)=0\) 当且仅当 \(E=\varnothing\) 而 \(\text{Prob}(E)=1\) 当且仅当 \(E=S\)。
3 鸽巢原理
\(\color{plum}\texttt{Watch the ceiling}\)
\(\color{violet}\texttt{Try to draw the line between what you need and}\)
\(\color{magenta}\texttt{I couldn't see it}\)
3.1 简单形式
3.1.1
如果要把 \(n+1\) 个物品放进 \(n\) 个盒子里，那么至少有一个盒子包含两个或更多的物品。
证明 用反证法。如果这 \(n\) 个盒子中每个都之多含有一个物品，那么物品的总数最多是 \(n\)， 与有 \(n+1\) 个物品矛盾，所以某个盒子至少有两个物品。\(\square\)
3.2 加强形式
3.1.1 是 3.2.1 的特殊情况。
3.2.1
设 \(q_1,q_2,\cdots,q_n\) 为正整数如果将 \(\sum_q-n+1\) 个物体放入 \(n\) 个盒子内，那么或者第一个盒子至少含有 \(q_1\) 个物品，\(\cdots\)，或者第 \(n\) 个和字至少含有 \(q_n\) 个物体。
证明 用反证法。假设我们把 \(\sum_q-n+1\) 个物体分别放到 \(n\) 个盒子中。\(\forall i=1,2,\cdots,n\)，第 \(i\) 个盒子有少于 \(q_i\) 个物品，那么所有盒子含有的总数不超过 \((q_1-1)+(q_2-1)+\cdots+(q_n-1)=\sum_q-n\)，矛盾。
3.2.2 平均原理
设 \(n\) 和 \(r\) 如果把 \(n(r-1)+1\) 个物品分配到 \(n\) 个盒子中，那么至少有一个盒子含有 \(r\) 个或更多的物品。或者说，若 \(n\) 个非负整数 \(m_1,m_2,\cdots,m_n\) 的平均数大于 \(r_1\)，即：
\[\dfrac{m_1+m_2+\cdots+m_2}{n}>r-1 \]那么至少有一个整数大于或等于 \(r\)。
证明 将 3.2.1 中的 \(\{q\}\) 全部赋值为 \(r\)。\(\square\)
Ramsey 定理
先鸽着。
4 二项式系数
\(\color{plum}\texttt{So when you feel broken}\)
\(\color{violet}\texttt{And you find nothing left to lose}\)
\(\color{magenta}\texttt{Let me take all the way over you}\)
\(\binom{n}{k}\) 计数 \(n\) 元集合的 \(k\) 子集的个数。由于它们出现在二项式定理中，因此也称之为二项式系数。
4.1 帕斯卡三角形
如下（\(\text{Pascal's triangle}\)）：
\[\begin{aligned}&1\\1\ &\ \ \ 1\\1\quad &2\quad 1\\1\quad 3\ &\ \ \ 3\quad 1\\1\quad 4\quad &6\quad 4\quad 1\\ &\vdots\end{aligned} \]4.2 二项式定理
二项式系数的名字来组它们在二项式定理中的使用。该定理最初的几种情形是若干为人熟知的代数式。
4.2.1
设 \(n\) 为正整数，对于所有的 \(x,y\)，均有：
\[(x+y)^n=\sum\limits_{k=0}^n\dbinom{n}{k}x^{n-k}y^k \]证明 考虑归纳法。若 \(n=1\)，等式显然成立：
\[(x+y)^1=\sum\limits_{k=0}^n\dbinom{1}{k}x^{1-k}y^k=\dbinom{1}{0}x^1y^0+\dbinom{1}{1}x^0y^1=x+y \]现在假设该等式对正整数 \(n\) 成立，证明用 \(n+1\) 代替 \(n\) 时等式依然成立。首先有：
\[(x+y)^{n+1}=(x+y)(x+y)^n \]因此：
\[\begin{aligned}(x+y)^{n+1}&=(x+y)\sum\limits_{k=0}^n\dbinom{n}{k}x^{n-k}y^k\\ &=x\left(\sum\limits_{k=0}^n\dbinom{n}{k}x^{n-k}y^k\right)+y\left(\sum\limits_{k=0}^n\dbinom{n}{k}x^{n-k}y^k\right)\\ &=\sum\limits_{k=0}^n\dbinom{n}{k}x^{n+1-k}y^k+\sum\limits_{k=0}^n\dbinom{n}{k}x^{n-k}y^{k+1}\\ &=\left(\dbinom{n}{0}x^{n+1}+\sum\limits_{k=1}^n\dbinom{n}{k}x^{n+1-k}y^k\right)+\left(\dbinom{n}{n}y^{n+1}+\sum\limits_{k=0}^{n-1}\dbinom{n}{k}x^{n-k}y^{k+1}\right) \end{aligned}\]对于上式的最后一项，用 \(k-1\) 代替 \(k\)，得到：
\[\sum\limits_{k=0}^{n-1}\dbinom{n}{k}x^{n-k}y^{k+1}=\sum\limits_{k=1}^{n}\dbinom{n}{k-1}x^{n+1-k}y^{k} \]因此：
\[\begin{aligned}(x+y)^{n+1}&=\sum\limits_{k=1}^{n}\left[\dbinom{n}{k}+\dbinom{n}{k-1}\right]x^{n+1-k}y^k+x^{n+1}+y^{n+1}\\ &=\sum\limits_{k=1}^{n}\dbinom{n+1}{k}x^{n+1-k}y^k+x^{n+1}+y^{n+1}\\ &=\sum\limits_{k=0}^{n+1}\dbinom{n+1}{k}x^{n+1-k}y^k \end{aligned}\]所以等式成立。\(\square\)
4.2.2
设 \(n\) 是正整数。对于所有的 \(x\) 均有：
\[(1+x)^n=\sum\limits_{k=0}^n\dbinom{n}{k}x^k=\sum\limits_{k=0}^n\dbinom{n}{n-k}x^k \]证明 将 4.2.1 中的 \(y\) 赋值为 \(1\)。
在 \(n=2,3,4\) 时，二项式定理的特殊情况分别是：
\[\begin{aligned}(x+y)^2&=x^2+2xy+y^2\\(x+y)^3&=x^3+3x^2y+3xy^2+y^3\\(x+y)^4&=x^4+4x^3y+6x^2y^2+4xy^3+y^4\end{aligned} \]不难发现，上面这些展开式中出现的系数就是帕斯卡三角形相应行上的数。
4.2.3 大的要来了
- 接下来，考虑二项式系数所满足的其他一些等式。
这个式子可以利用这样的事实立即得到证明：
\[\begin{aligned}\dbinom{n}{k}&=\dfrac{n(n-1)\cdots(n-k+1)}{k(k-1)\\\cdots 1}\end{aligned} \]乘上 \(k\) 就为原式。
\[\dbinom{n}{0}+\dbinom{n}{1}+\dbinom{n}{2}+\cdots+\dbinom{n}{n}=2^n\quad(n\geq 0)\tag{4.2} \]根据二项式定理，设 \(x=y=1\) 而证明它是成立的。如果在二项式定理中设 \(x=1,y=-1\)，则可以得到下面的交错和：
\[\dbinom{n}{0}-\dbinom{n}{1}+\dbinom{n}{2}-\cdots+(-1)^n\dbinom{n}{n}=0\quad(n\geq1)\tag{4.3} \]把带有负号的项移到等号右边，得：
\[\dbinom{n}{0}+\dbinom{n}{2}+\cdots=\dbinom{n}{1}+\dbinom{n}{3}+\cdots\quad(n\geq 1)\tag{4.4} \]这个东西也可以这样理解：如果 \(S\) 是 \(n\) 元集合，则有偶数个元素的 \(S\) 子集的数目等于有奇数个元素的 \(S\) 子集的数目。因为这两个的和相等，再根据等式 \(\left(2\right)\)，它们的和为 \(2^n\)，所以这两个的和等于 \(2^{n-1}\)，即：
\[\dbinom{n}{0}+\dbinom{n}{2}+\cdots=2^{n-1}\tag{4.5} \]\[\dbinom{n}{1}+\dbinom{n}{3}+\cdots=2^{n-1}\tag{4.6} \]利用等式 \(\left(1\right)\) 和 \(\left(2\right)\) 可以导出下面的等式：
\[1\dbinom{n}{1}+2\dbinom{n}{2}+\cdots+n\dbinom{n}{n}=n2^{n-1}\quad(n\geq 1)\tag{4.7} \]为了证明它，首先不难发现根据 \((1)\) 式，上式与以下等价：
\[n\dbinom{n-1}{0}+n\dbinom{n-1}{1}+\cdots+n\dbinom{n-1}{n-1}=n2^{n-1}\quad(n\geq 1)\tag{4.8} \]在 \((2)\) 中用 \(n-1\) 替换 \(n\) 得到：
\[n\dbinom{n-1}{0}+n\dbinom{n-1}{1}+\cdots+n\dbinom{n-1}{n-1}=n\left(\dbinom{n-1}{0}+\dbinom{n-1}{1}+\cdots+\dbinom{n-1}{n-1}\right)=n2^{n-1} \]所以 \((8)\) 式成立，进而 \((9)\) 式成立。
- 许多等式都可以通过连续求导及关于 \(x\) 的乘法展开得到。从 4.2.2 的等式开始：
将它两边关于 \(x\) 求导，得到：
\[n(1+x)^{n-1}=\sum\limits_{k=1}^{n}k\dbinom{n}{k}x^{k-1}\tag{4.10} \]把 \(x=1\) 带入就是 \((7)\) 式。在 \((10)\) 式两边乘上 \(x\) 得到：
\[nx(1+x)^{n-1}=\sum\limits_{k=1}^nk\dbinom{n}{k}x^k\tag{4.11} \]两边求导得：
\[n\left[(1+x)^{n-1}+(n-1)x(1+x)^{n-2}\right]=\sum\limits_{k=1}^{n}k^2\dbinom{n}{k}x^{k-1}\tag{4.12} \]将 \(x=1\) 带入得：
\[n\left[2^{n-1}+(n-1)2^{n-2}\right]=\sum\limits_{k-1}^{n}k^2\dbinom{n}{k}\tag{4.13} \]所以有：
\[n(n+1)2^{n-2}=\sum\limits_{k=1}^n k^2\dbinom{n}{k}\tag{4.14} \]从 \((9)\) 式开始，通过交替关于 \(x\) 求导并乘以 \(x\)，我们可以得到 \(\sum\limits_{k=1}^{n}k^p\dbinom{n}{k}\) 相对于任何正整数 \(p\) 的恒等式，但随着 \(p\) 的增长，这将变得很不平凡。
- 关于帕斯卡三角形上的各数字的平方和，可以得到下面这样的等式：
考虑组合推理。设 \(S\) 是一个 \(2n\) 元集合，等号右边计数 \(S\) 的 \(n\) 子集的数目。我们把 \(S\) 划分为 \(A\) 和 \(B\) 两个子集，每一个子集都有 \(n\) 个元素。利用 \(S\) 的划分来划分 \(S\) 的 \(n\) 子集。\(S\) 的每一个 \(n\) 子集包含 \(k\) 个 \(A\) 的元素和 \(n-k\) 个 \(B\) 的元素。
将 \(S\) 的 \(n\) 子集划分为 \(n+1\) 个部分：
\[C_0,C_1,C_2,\cdots,C_n \]其中 \(C_k\) 是由包含 \(k\) 个 \(A\) 的元素和 \(n-k\) 个 \(B\) 的元素组成的 \(n\) 子集。根据加法原理，有：
\[\dbinom{2n}{n}=\lvert C_0\rvert+\lvert C_1\rvert+\lvert C_2\rvert+\cdots+\lvert C_n\rvert\tag{4.16} \]\(C_k\) 的 \(n\) 子集可以通过从 \(A\) 中选择 \(k\) 个元素并从 \(B\) 中选择 \(n-k\) 个元素而得到。因此根据乘法原理有：
\[\lvert C_k\rvert=\dbinom{n}{k}\dbinom{n}{n-k}=\dbinom{n}{k}^2\quad(n=0,1,\cdots,n) \]带入到 \((16)\)：可证明 \(15\) 成立，这也是范德蒙德卷积的特殊形式。它的一般情况为：
\[\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}\tag{4.17} \]二项式定理或组合意义都可证。
- 现在扩展 \(\binom{n}{k}\) 的定义范围，允许 \(n\) 为任意实数，\(k\) 为任意整数。
所以有：
\[\dbinom{n}{k}=\begin{cases}\dfrac{n(n-1)\cdots(n-k+1)(k\leq 1)}{k!}\quad &(k\geq1)\\1&(k=0)\\0&(k\leq -1)\end{cases} \]考虑帕斯卡公式：
\[\dbinom{n}{k}=\dbinom{n-1}{k}+\dbinom{n-1}{k-1} \]我们不断将后一项运用公式，不断迭代后可得到：
\[\dbinom{n}{0}+\dbinom{n+1}{1}+\cdots+\dbinom{n+k}{k}=\dbinom{n+k+1}{k}\tag{4.18} \]将前一项不断迭代可得到：
\[\dbinom{0}{k}+\dbinom{1}{k}+\cdots+\dbinom{n}{k}=\dbinom{n+1}{k+1}\tag{4.19} \]4.3 二项式系数的单峰性
观察帕斯卡三角形某一行上的二项式系数，发现这些系数先递增后递。据哟这种性质的树枝序列称作为单峰的 \((\text{unimodal})\)。
因此，如果存在一个整数 \(t\)，且 \(0\leq t\leq n\)，使得：
\[s_0\leq s_1\leq \cdots\leq s_t,s_t\geq s_t+1\geq\cdots\geq s_n \]那么序列 \(\{s\}\) 就是单峰的。其中 \(s_t\) 是序列的最大数，\(t\) 不唯一。
4.3.1
设 \(n\) 为正整数，那么二项式序列：
\[\dbinom{n}{0},\dbinom{n}{1},\cdots,\dbinom{n}{n} \]是单峰的。
证明 考虑序列中连续两个二项式系数的商。令 \(k\in\left[1,n\right]\)。于是有：
\[\dfrac{\dbinom{n}{k}}{\dbinom{n}{k-1}}=\dfrac{\dfrac{n!}{k!(n-k)!}}{\dfrac{n!}{(k-1)!(n-k+1)!}}=\dfrac{n-k+1}{k} \]根据 \(k\) 和 \(n-k+1\) 的大小关系，分别有：
\[\begin{aligned}&<&&<\\k&=n-k+1&\Rightarrow\ \ \dbinom{n}{k-1}&=\dbinom{n}{k}\\&>&&>\end{aligned} \]因此得证。\(\square\)
4.4 牛顿二项式定理
4.4.1
设 \(\alpha\) 为实数。对于所有满许 \(0\leq\lvert x\rvert<\lvert y\rvert\) 的 \(x\) 和 \(y\)，均有：
\[(x+y)^{\alpha}=\sum\limits_{k=0}^{\infty}\dbinom{\alpha}{k}x^ky^{\alpha-k} \]证明
我不会。读者自证不难。\(\square\)
若 \(z=x/y\),则 \((x+y)^{\alpha}=y^{\alpha}(1+z)^{\alpha}\)。所以可以等价转述为：对于满足 \(\lvert z \rvert<1\) 的任意 \(z\)，均有：
\[(1+z)^{\alpha}=\sum\limits_{k=0}^{\infty}\dbinom{\alpha}{k}z^k \]令 \(\alpha\) 为负整数 \(-n\)，可以得到：
\[(1+z)^{-n}=\dfrac{1}{(1+z)^{n}}=\sum\limits_{k=0}^{\infty}(-1)^k\dbinom{n+k-1}{k}z^k\tag{4.20} \]\(-z\) 代替 \(z\) 可以得到：
\[(1-z)^{-n}=\dfrac{1}{(1-z)^{n}}=\sum\limits_{k=0}^{\infty}\dbinom{n+k-1}{k}z^k\tag{4.21} \]将 \(n=1\)带入到 \((4.20),(4.21)\)，那么得到：
\[\dfrac{1}{1+z}=\sum\limits_{k=0}^{\infty}(-1)^kz^k\quad(\lvert z\rvert<1)\tag{4.22} \]和：
\[\dfrac{1}{1-z}=\sum\limits_{k=0}^{\infty}z^k\quad(\lvert z\rvert<1)\tag{4.23} \]二项式定理可以用来得到任意精度的平方根。如果取 \(\alpha=\frac{1}{2}\)，那么对于 \(k>0\) 有：
\[\begin{aligned}\dbinom{\alpha}{k}=\dbinom{1/2}{k}&=\dfrac{\dfrac{1}{2}(\dfrac{1}{2}-1)\cdots(\dfrac{1}{2}-k+1)}{k!}\\&=\dfrac{(-1)^{k-1}}{2^k}\dfrac{1\times2\times3\times\cdots\times{2k-2}}{2\times4\times\cdots(2k-2)\times(k!)}\\&=\dfrac{(-1)^{k-1}}{k\times 2^{2k-1}}\dfrac{(2k-2)!}{(k-1)!^2}=\dfrac{(-1)^{k-1}}{k\times 2^{2k-1}}\dbinom{2k-2}{k-1}\end{aligned} \]因此，对于 \(\lvert z\rvert<1\) 有：
\[\sqrt{1+z}=1+\sum\limits_{k=1}^{\infty}\dfrac{(-1)^{k-1}}{k\times 2^{2k-1}}\dbinom{2k-2}{k-1}z^k=1+\dfrac{1}{2}z-\dfrac{1}{2\times 2^3}\dbinom{2}{1}z^2+\dfrac{1}{3\times 2^5}\dbinom{4}{2}z^3-\cdots \]随着项数的增加，精度随之提高。
5 容斥原理
\(\color{plum}\texttt{If you crash into the ocean}\)
\(\color{violet}\texttt{No one's gonna save you like I do}\)
\(\color{magenta}\texttt{Take a chance, take my hand, I got you}\)
5.1 容斥
容斥原理相对于加法原理更加复杂，但也有更广泛的应用，它对集合之间是否相交没有限制。
5.1.1
集合 \(S\) 中不具有性质 \(P_1,P_2,\cdots,P_m\) 的对象个数为：
\[\lvert\overline{A}_1\cap\overline{A}_2\cap\cdots\cup\overline{A}_m\rvert=\lvert S\rvert-\sum\lvert A_i\rvert+\sum\lvert A_i\cap A_j\rvert-\cdots+(-1)^m\lvert A_1\cap A_2\cap\cdots\cap A_m\rvert \]一般情况下，等号右边的项数为：
\[\sum\limits_{k=0}^{m}\dbinom{m}{k}=2^m \]证明 要证等式成立即正不具性质 \(P_1,P_2,\cdots,P_m\) 中任何一个对象对这个等式的右边的净贡献为 \(1\)，而至少具有一条的一个对象的净贡献为 \(0\)。
\[1-0+0-\cdots+(-1)^m0=1 \]
首先，设对象 \(x\) 不具有任何一条性质，显然它的贡献为：考虑有 \(n\leq 1\) 条性质的对象 \(y\)。\(y\) 对 \(S\) 的贡献是 \(1=\binom{n}{0}\)。因为 \(y\) 恰有 \(n\) 条性质，因此它也是 \(A_1,A_2,\cdots,A_m\) 中 \(n\) 个集合的成员，对 \(\sum\lvert A_i\rvert\) 的贡献为 \(\dbinom{n}{1}\)。
\[\dbinom{n}{0}-\dbinom{n}{1}+\cdots+(-1)^m\dbinom{n}{m} \]
以此类推，\(y\) 对右边的净贡献为：由于 \(n\leq m\) 所以上式等于：
\[\dbinom{n}{0}-\dbinom{n}{1}+\cdots+(-1)^n\dbinom{n}{n}=0 \]等于零的原因在 \((4.3)\)。\(\square\)
6.1.2
集合中至少具有性质 \(P_1,P_2,\cdots,P_m\) 之一的对象个数为：
\[\lvert A_1\cap A_2\cap\cdots\cup A_m\rvert=\sum\lvert A_i\rvert-\sum\lvert A_i\cap A_j\rvert+\cdots+(-1)^m\lvert A_1\cap A_2\cap\cdots\cap A_m\rvert \]标签：入门,rvert,dfrac,sum,lvert,cdots,数学,进门,dbinom From： https://www.cnblogs.com/QcpyWcpyQ/p/18017165证明 $$\lvert\overline{A}_1\cap\overline{A}_2\cap\cdots\cup\overline{A}_m\rvert=\lvert S\rvert-\sum\lvert A_i\rvert+\sum\lvert A_i\cap A_j\rvert-\cdots+(-1)^m\lvert A_1\cap A_2\cap\cdots\cap A_m\rvert \square$$