227 lines
10 KiB
TeX
227 lines
10 KiB
TeX
\chapter{组合工具}
|
||
\section{归纳法（略）}
|
||
见《线性代数》。
|
||
|
||
\section{估算}
|
||
阶乘的估算：$n!$随$n$的增大增长迅速。粗略地估计，有$2^{n-1} \leq n! \leq n^{n-1}$。
|
||
|
||
Stirling给出了一个近似公式：$n! \sim \sqrt{2\pi n} \left(\dfrac{n}{e}\right)^n$。
|
||
|
||
思路：左边取对数：
|
||
\begin{equation*}
|
||
\sum \ln{n} \approx \int_1^n \ln{x} \dif x = n \ln{n} - n + 1 \eqper
|
||
\end{equation*}
|
||
$n\ln{n}$即为$\left(\dfrac{n}{e}\right)^n$取对数，$\sqrt{2 \pi n}$则是一个为了弥补积分与黎曼和的差距的系数。
|
||
|
||
相对误差：$\toinf \dfrac{n!}{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n} = 1$；
|
||
|
||
绝对误差：$\toinf \left[n! - \sqrt{2 \pi n} \left(\dfrac{n}{e}\right)^n\right] = +\infty$。
|
||
|
||
\section{容斥原理}
|
||
\subsection{引言}
|
||
容斥原理研究与集合交、并、差有关的技术。在一些问题中，间接计算比直接计算来得简单。
|
||
|
||
\subsection{容斥原理}
|
||
\begin{theorem}[两个集合的容斥原理]
|
||
设$A$和$B$是两个有限的集合，则
|
||
\begin{equation*}
|
||
\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert \eqper
|
||
\end{equation*}
|
||
\end{theorem}
|
||
|
||
\begin{corollary}[加法原理]
|
||
若$A \cap B = \varnothing$，则$\vert A \cup B \vert = \vert A \vert + \vert B \vert$
|
||
\end{corollary}
|
||
|
||
\begin{corollary}[减法原理]
|
||
$\vert A \vert = \vert E \vert - \vert A^\mathrm{C} \vert $，$\vert A^\mathrm{C} \vert = \vert E \vert - \vert A \vert$。
|
||
\end{corollary}
|
||
|
||
\begin{theorem}[三个集合上的容斥原理]
|
||
$A$，$B$，$C$为任意有限集合，有
|
||
\begin{equation*}
|
||
\vert A \cup B \cup C \vert = \vert A \vert + \vert B \vert + \vert C \vert - \vert A \cap B \vert - \vert B \cap C \vert - \vert A \cap C \vert + \vert A \cap B \cap C \vert
|
||
\end{equation*}
|
||
\end{theorem}
|
||
|
||
\begin{theorem}[$n$个集合上的容斥原理]
|
||
$A_1, A_2, \dots , A_n$是有限集合。
|
||
\begin{equation*}
|
||
\begin{aligned}
|
||
\vert A_1 \cup A_2 \cup \dots \cup A_n \vert & = \sum_i^n \vert A_i \vert - \sum_i^n \sum_{j > i} \vert A_i \cap A_j \vert + \sum_i^n \sum_{j>i} \sum_{k > j} \vert A_i \cap A_j \cap A_k \vert - \dots\\
|
||
& + (-1)^{n-1}\vert A_1 \cap A_2 \cap \dots \cap A_n \vert \eqper
|
||
\end{aligned}
|
||
\end{equation*}
|
||
\end{theorem}
|
||
|
||
\begin{theorem}[容斥原理的补集形式]
|
||
\begin{equation*}
|
||
\vert A_1^\mathrm{C} \cap A_2^\mathrm{C} \cap \dots \cap A_n^\mathrm{C}\vert = \vert E \vert - \vert A_1 \cup A_2 \cup \dots \cup A_n \vert \eqper
|
||
\end{equation*}
|
||
\end{theorem}
|
||
|
||
\subsection{容斥原理的应用}
|
||
\subsubsection{错排问题}
|
||
给定$n$个元素的一个排列，使得所有的元素都不在原来的位置上的排列叫做原排列的{\bf{错排}}。
|
||
|
||
\emph{应用加法原理：}
|
||
设$1, 2, \dots , n$的的错排数为$D_n$，那么错排可通过如下两种方式得到：
|
||
\begin{enumerate}[label=({\arabic*}) ]
|
||
\item 把$n$与$i (i = 1, 2, \dots, n-1)$互换，再让剩余$n-2$个数进行错排。共有$(n-1)D_{n-2}$种。
|
||
\item 让$1, 2, \dots , n-1$任意排列，然后把$n$分别与错排后的第1个、第2个……第$n-1$个交换。共有$(n-1)D_{n-1}$种。
|
||
\end{enumerate}
|
||
|
||
综上，由加法原理，有$D_n = (n-1)D_{n-1} + (n-1)D_{n-2}$。由$D_1 = 0, D_2 = 1$，可得$D_0 = 1$。
|
||
|
||
估计：$(n-1)(D_{n-2} + D_{n-1}) \leq D_n \leq n!$，可以知道$D_n$与$n!$相差不大，因此可设
|
||
\begin{equation*}
|
||
D_n = E_n \cdot n! \eqco
|
||
\end{equation*}
|
||
即
|
||
\begin{equation*}
|
||
E_n = \dfrac{D_n}{n!}\eqper
|
||
\end{equation*}
|
||
|
||
那么有
|
||
\begin{equation*}
|
||
\begin{aligned}
|
||
E_n & = \dfrac{(n-1)(D_{n-2} + D_{n-1})}{n!}\\
|
||
& = \dfrac{n-1}{n} \cdot \dfrac{D_{n-1}}{(n-1)!} + \dfrac{1}{n} \cdot \dfrac{D_{n-2}}{(n-2)!}\\
|
||
& = \left(1 - \dfrac{1}{n}\right)E_{n-1} + \dfrac{1}{n} E_{n-2}
|
||
\end{aligned}
|
||
\end{equation*}
|
||
|
||
于是
|
||
\begin{equation*}
|
||
\begin{aligned}
|
||
E_n & = \left(1 - \dfrac{1}{n}\right)E_{n-1} + \dfrac{1}{n} E_{n-2}\\
|
||
E_n - E_{n-1} & = - \dfrac{1}{n}(E_{n-1} - E_{n-2})\\
|
||
& = \left(-\dfrac{1}{n}\right) \left(-\dfrac{1}{n-1}\right) (E_{n-2} - E_{n-3})\\
|
||
& = \dots\\
|
||
& = (-1)^{n-1} \dfrac{1}{n!}(E_1 - E_0)\\
|
||
& = \dfrac{(-1)^n}{n!}\eqper
|
||
\end{aligned}
|
||
\end{equation*}
|
||
|
||
因此
|
||
\begin{equation*}
|
||
\begin{aligned}
|
||
E_n & = \dfrac{(-1)^n}{n!} + E_{n-1}\\
|
||
& = \dfrac{(-1)^n}{n!} + \dfrac{(-1)^{n-1}}{(n-1)!} + E_{n-2}\\
|
||
& = \dots\\
|
||
& = \dfrac{(-1)^n}{n!} + \dfrac{(-1)^{n-1}}{(n-1)!} + \dots + \dfrac{(-1)^1}{2!} \eqper
|
||
\end{aligned}
|
||
\end{equation*}
|
||
|
||
即
|
||
\begin{equation*}
|
||
D_n = n!\cdot E_n = n!\left(1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + \dots + \dfrac{(-1)^n}{n!}\right) \approx \dfrac{n!}{e} \eqper
|
||
\end{equation*}
|
||
|
||
\emph{应用容斥原理：}设$E$：所有$n!$种排列的集合；$A_j$：$j$在第$j$位的排列的集合。那么所求错排的集合为
|
||
\begin{equation*}
|
||
A_1^\mathrm{C} \cap A_2^\mathrm{C} \cap \dots \cap A_n^\mathrm{C} \eqper
|
||
\end{equation*}
|
||
|
||
另外可以看到，
|
||
\begin{equation*}
|
||
\begin{aligned}
|
||
\vert A_j \vert & = (n-1)! \eqco j = 1, 2, \dots, n\\
|
||
\vert A_i \cap A_j \vert & = (n-2)! \eqco i, j = 1, 2, \dots, n \text{且} i \neq j\\
|
||
& \dots\\
|
||
\vert A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \vert & = (n - k)!\eqco\text{共有}\dbinom{n}{k}\text{种组合方式}
|
||
\end{aligned}
|
||
\end{equation*}
|
||
|
||
那么
|
||
\begin{equation*}
|
||
\begin{aligned}
|
||
D_n & = \vert A_1^\mathrm{C} \cap A_2^\mathrm{C} \cap \dots \cap A_n^\mathrm{C}\vert\\
|
||
& = n! - \dbinom{n}{1}(n-1)! + \dbinom{n}{2}(n-2)! - \dbinom{n}{3}(n-3)! + \dots + (-1)^n\dbinom{n}{n}0!\\
|
||
& = n! - \dfrac{n!}{1} + \dfrac{n!}{2} - \dfrac{n!}{3} + \dots + (-1)^n \dfrac{n!}{n!}\\
|
||
& = n! \left(1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + \dots + \dfrac{(-1)^n}{n!}\right) \eqper
|
||
\end{aligned}
|
||
\end{equation*}
|
||
|
||
\subsubsection{限制排列}
|
||
|
||
\subsubsection{相对禁位排列}
|
||
|
||
\section{鸽巢原理}
|
||
鸽巢原理是解决存在性问题的基本而有力的工具。
|
||
|
||
\begin{theorem}
|
||
若有$n+1$只鸽子飞回$n$个鸽巢，则至少有两只鸽子飞入了同一个鸽巢。
|
||
\end{theorem}
|
||
|
||
鸽巢原理只能证明某种安排或者某种现象存在，而并未指出怎样构造这样的安排或者怎样寻找这种现象出现的场合。
|
||
|
||
利用鸽巢原理解决问题的关键就在于看出要解决的问题是鸽巢问题，建立``鸽巢''，寻找``鸽子''。
|
||
|
||
\begin{example}
|
||
在一个边长为1的正三角形中任意取5个点，必然有两个点之间的距离不超过$\dfrac{1}{2}$。
|
||
\end{example}
|
||
\begin{proof}
|
||
将三角形三边的终点连接，可以将三角形等分成四块。在三角形中取五个点，则一定存在一个部分中有至少两个点。这两个点之间的距离小于$\dfrac{1}{2}$。
|
||
\end{proof}
|
||
|
||
\begin{theorem}
|
||
设$m_1, m_2, \dots , m_n$均为正整数，如果有$m_1 + m_2 + \dots + m_n - n + 1$只鸽子飞回$n$个鸽巢，则或者第1个鸽巢至少有$m_1$只鸽子，则或者第2个鸽巢至少有$m_2$只鸽子，……，则或者第$n$个鸽巢至少有$m_n$只鸽子。
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
（反证法）假若第1鸽巢少于$m_1$只鸽子，第2鸽巢少于$m_2$只鸽子，……，第n鸽巢少于$m_n$只鸽子，则鸽子总数至多为：
|
||
\begin{equation*}
|
||
(m_1 - 1) + (m_2 - 1) + \dots + (m_n - 1) = m_1 + m_2 + \dots + m_n -n \eqco
|
||
\end{equation*}
|
||
这比假定的鸽子数少了一个，矛盾！
|
||
\end{proof}
|
||
|
||
\begin{corollary}
|
||
如果$m_1 = m_2 = \dots = m_n = r$，若将$n(r-1)+1$个球放入$n$个盒子中，则至少有一个盒子含有不少于$r$个球。
|
||
\end{corollary}
|
||
|
||
\begin{corollary}
|
||
如果$n$个正整数$m_1, m_2, \dots , m_n$的平均数$\dfrac{m_1 + m_2 + \dots + m_n}{n} > r-1$，则$m_1, m_2, \dots, m_n$中至少有一个不会小于$r$。
|
||
\end{corollary}
|
||
|
||
\begin{corollary}
|
||
有$m$个球放入$n$个盒子，则至少有一个盒子中有不少于$\lfloor \dfrac{m-1}{n}\rfloor + 1$个球。
|
||
\end{corollary}
|
||
|
||
\begin{theorem}[Erdös]
|
||
由$n^2 + 1$个不同实数构成的数列中，存在一个至少有$n+1$项的单调递增子数列或单调递减子数列。
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
设原数列为$a_1, a_2, \dots , a_n$。
|
||
|
||
令$m_i$表示以$a_i$为第一项的最长递增子列的长度。若有某个$m_i \geq n+1$，则定理得证；
|
||
|
||
若所有的$m_i$都小于$n+1$，那么所有的$n^2 + 1$个$m_i$必然都在$1$到$n$之间，这相当于把$n^2 + 1$个球放进$n$个盒子里，于是一定有至少有$n+1$个$m_i$相等。我们不妨设$m_{i_1} = m_{i_2} = \dots = m_{i_{n+1}} = m$，且$1 \leq i_1 < i_2 < \dots < i_{n+1} \leq n^2 + 1$。
|
||
|
||
注意到，对任意的$i_j, i_k(j < k)$，当$m_{i_j} = m_{i_k}$时，有$a_{i_j} > a_{i_k}$。这是因为假若$a_{i_j} < a_{i_k}$（题目已申明$\{a_n\}$中数字各不相同，因此两个项不可能相等），那么我们可以将以$a_{i_k}$为第一项的、长度为$m$的递增子数列放在$a_{i_j}$后面得到一个长度为$m+1$的递增子数列，那么$m_{i_j}$就不是$m_{i_k}$而是$m_{i_k}+1$了，这与$m_{i_j} = m_{i_k}$矛盾。因此，$a_{i_1} > a_{i_2} > \dots > a_{i_{n+1}}$。
|
||
|
||
因此我们可以找到如下长度为$n+1$的递减子数列：$a_{i_1} , a_{i_2} , \dots , a_{i_{n+1}}$。
|
||
\end{proof}
|
||
|
||
\section{The Twin Paradox生日悖论}
|
||
随机找$n(n < 365)$名学生，问有多大可能两人在同一天过生日？
|
||
|
||
\begin{proof}[解]
|
||
设$A$：有两个人在同一天过生日。
|
||
|
||
则$A^\mathrm{C}$：所有学生生日彼此不同。
|
||
|
||
\begin{equation*}
|
||
\begin{aligned}
|
||
\vert A^\mathrm{C} \vert & = 365 \times 364 \times \dots \times (365-n+1)\\
|
||
P(A) & = 1 - P(\setcom{A}) = 1 - \dfrac{\vert \setcom{A} \vert}{365^n}\\
|
||
& = 1 - \dfrac{365 \times 364 \times \dots \times (365-n+1)}{365^n}\\
|
||
& = 1 - \left(1 - \dfrac{1}{365}\right) \left(1 - \dfrac{2}{365}\right) \dots \left(1 - \dfrac{n-1}{365}\right)\eqper
|
||
\end{aligned}
|
||
\end{equation*}
|
||
|
||
当$n=22$时，$P(n)$就已经达到了47.57\%；当$n=70$时，$P(n)$则为99.92\%。
|
||
\end{proof}
|