于是他迟到的组合数学学习开始了

larry76 / 2023-05-03 / 原文

加法原理

完成一件事，有 \(m\) 类方法，对于每类方法有 \(s_i\) 个方案，则此时总方案数就是 \(\sum_{i=1}^m s_i\)。

乘法原理

完成一件事，有 \(n\) 个步骤，对于每个步骤有 \(s_i\) 个方案，则此时总方案数就是 \(\prod_{i=1}^n s_i\)。

排列

从 \(n\) 个数中选出 \(m\) 个数的一个排列，记作 \(A_n^m\)，易得：

\[A_n^m = \prod_{i=0}^{m-1} (n-i) = \dfrac {n!}{(n-m)!} \]

则显然，全排列（从 \(n\) 个数中选出 \(n\) 个数）的方案数为 \(n!\)。

组合

从 \(n\) 个数中选出 \(m\) 个数的一个组合，记作 \(C_n^m\) 或 \(\dbinom{n}{m}\)，易得：

\[{n\choose m} = \dfrac {A_n^m}{A_m^m} = \dfrac {n!}{m!(n-m)!} \]

\(\text{Lemma 1}\)：对称恒等式

\[\dbinom{n}{m} = \dbinom{n}{n-m} \]

\(\text{Lemma 2}\)：吸收恒等式

\[\dbinom nk = \dfrac nk\dbinom {n-1}{k-1} \]

\(\text{Lemma 3}\)：加法公式

\[\dbinom {n}{m} = \dbinom {n-1}{m} + \dbinom {n-1}{m-1} \]

\(\text{Lemma 4}\)：二项式定理，但是 \(a=1\) 且 \(b=1\)

\[\sum_{i=1}^n \dbinom {n}{i} = 2^n \]

\(\text{Lemma 5}\)：二项式定理，但是 \(a=1\) 且 \(b=-1\)

\[\sum_{i=0}^n (-1)^i \dbinom {n}{i} = [n=0] \]

\(\text{Lemma 6}\)：平行求和法

\[\sum_{k\le n} \dbinom{r+k}{k} = \dbinom{r+n+1}{n} \]

\(\text{Lemma 7}\)：上指标求和法

\[\sum_{0\le k \le n} \dbinom{k}{m} = \dbinom{n+1}{m+1}\quad (n,m\ge 0) \]

\(\text{Lemma 8}\)：上指标反转

\[\dbinom{r}{k} = (-1)^k\dbinom{k-r-1}{k} \]

\(\text{Lemma 9}\)：交换恒等式

\[\dbinom{r}{m}\dbinom{m}{k} = \dbinom{r}{k} \dbinom{r-k}{m-k} \]

\(\text{Lemma 10}\)：范德蒙德卷积

\[\sum_{k}\dbinom{r}{m+k}\dbinom{s}{n-k} = \dbinom{r+s}{m+n} \]

\(\text{Lemma 11}\)：

\[\sum_{-l\le k \le r} \dbinom{r-k}{m} \dbinom{l+k}{n} = \dbinom{l+r+1}{m+n+1}\quad(l+q,n,m\ge 0) \]

\(\text{Lemma 12}\)：

\[\sum_{i=0}^n i \dbinom{n}{i} = n2^{n-1} \]

\(\text{Lemma 13}\)：

\[\sum_{i=0}^n i^2 \dbinom{n}{i} = n(n-1)2^{n-2} \]

\(\text{Lemma 14}\)：

\[\sum_{i=0}^n \dbinom{i}{k} = \dbinom{n+1}{k+1} \]

\(\text{Lemma 15}\)：其中的 \(f_x\) 为第 \(x\) 项的普通斐波那契数列

\[\sum_{i=0}^n \dbinom{n-i}{i} = f_{n+1} \]

可重复排列

从 \(n\) 个数中选出 \(m\) 个数的一个排列，允许同一个数多次取出，可以得出，其排列数为 \(n^m\)。

可重复组合

从 \(n\) 个数中选出 \(m\) 个数的一个组合，允许同一个数多次取出，可以得出，其组合数为 \(\dbinom {n+m-1}{m}\)。

不全相异元素的全排列

从 \(n\) 个数中选出 \(m\) 个数的一个排列，且 \(n\) 个元素中，分别有 \(n_1,\,n_2,\, \cdots,\, n_k\) 个元素相同，且 \(\sum_{i=1}^k n_i = n\)，则其全排列为不全相异元素的全排列，其排列数记为 \(\dbinom {n}{n_1\, n_2\, \cdots\, n_k}\)，可知其等于 \(\dfrac {n!}{\prod_{i=1}^k n_i!}\)。

多组组合

把 \(n\) 个不同的数分成 \(k\) 组，且这 \(k\) 个组按照一定的顺序排列，其中第 \(i\) 组（\(i \in [1,k]\)）有 \(n_i\) 个元素，且 \(\sum_{i=1}^k n_i = n\)，则不同的分组方法的种数为 \(\dbinom{n}{n_1\, n_2\, \cdots\, n_k}\)，可知其等于 \(\dfrac {n!}{\prod_{i=1}^k n_i!}\)。

这里给出一个很 \(\text{OIer}\) 的口胡证明：

考虑对分成的组内进行染色，处于相同组的元素将会被染成同样的颜色，则此时原问题可以被转化为不全相异元素的全排列。

证毕。

圆排列

将 \(n\) 个不同的元素不分首尾排成一圈，其排列数为 \((n-1)!\)，证明显然。

项链数

将 \(n\) 粒不同的珠子串成一条项链，则能得到的不同的项链数为 \(\lceil \dfrac 12 (n-1)!\rceil\)。

一类不定方程的非负整数解个数

不定方程 \(\sum_{i=1}^m x_i = n\;(m,n\in \mathbb{N}_+)\) 的非负整数解 \([x_1,x_2,\cdots,x_m]\) 的个数为 \(\dbinom {n+m-1}{m-1}\)。

注意：其与可重复组合的计数是相同的。

\(\text{Lemma}\)

不定方程 \(\sum_{i=1}^m x_i = n\;(m,n \in \mathbb{N_+},\,m\le n)\) 的正整数解 \([x_1,x_2,\cdots, x_m]\) 的个数为 \(\dbinom {n-1}{m-1}\)

证明：

\[\begin{aligned} &\text{令 }y_i = x_i-1,\, \text{则 } \sum_{i=1}^m y_i = n-m\\ &\text{则新方程的非负整数解个数等价于原问题}\\ &\text{故：}S= {n-m+m-1 \choose m-1} = {n-1 \choose m-1} \end{aligned} \]

容斥原理

设 \(A_1,\,A_2,\,\cdots,\,A_n\) 为有限集合，用 \(\mid A_i\mid\) 表示集合 \(A_i\) 的大小，则：

\[\mid \bigcup_{i=1}^{n} A_i\mid = \sum_{m=1}^n (-1)^{m-1} \sum_{a_i<a_{i+1}}\mid \bigcap_{i=1}^m A_{a_i}\mid \]

逐步淘汰原理（筛法公式）

设 \(S\) 为有限集合，\(A_i \subset S\;(i\in[1,n])\)，\(A_i\) 在 \(S\) 中的补集为 \(\complement_SA_i\;(i\in [1,n])\) 则

\[{\mid \bigcap_{i=1}^n \complement_S A_i\mid} = {\mid S \mid} - \sum_{m=1}^n (-1)^{m-1}\sum_{a_i < a_{i+1}} \mid \bigcap_{i=1}^m A_{a_i} \mid \]

注意： 逐步淘汰原理和容斥原理是一个思想，他们统称为包含与排除原理，我们也可以统称为容斥原理。

置换及其不动点

给定集合 \(X = \{1,\,2,\,3,\,\cdots,\,n\}\)，\(\varphi\) 是从 \(X\) 到 \(X\) 上的一一映射，通常记为：

\[\varphi = \begin{Bmatrix} 1& 2 & \cdots & n \\ \varphi(1) & \varphi(2) & \cdots & \varphi(n) \end{Bmatrix} \]

则称 \(\varphi\) 为 \(X\) 上的置换，其中 \(\varphi(i)\) 是元素 \(i\) 在 \(\varphi\) 下的象，因为是一一映射，所以 \(\varphi(1),\,\varphi(2),\,\cdots,\, \varphi(n)\) 实际上就是 \(X\) 的一个排列。

其中，满足 \(\varphi(i)=i\) 的数 \(i\) 为 \(\varphi\) 上的一个不动点。

我们可以尝试通过图论的角度来理解置换和不动点。

对于 \(X\)，将 \(X_{\varphi(i)}\) 向 \(X_i\) 连边，我们会发现此时图中会形成许多环，其中只有不动点的环为自环。

其中显然的是，\(X\) 的所有置换的数量为 \({\mid X\mid}!\)

\(\text{Lemma 1}\)

集合 \(X = {1,\,2,\,\cdots,\,n}\) 上没有任何不动点的置换 \(\varphi\) 的数量为：

\[D_n = n!\left[ 1-\dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + \cdots + \dfrac{(-1)^n}{n!} \right] = n! \cdot \sum_{i=0}^n (-1)^i \dfrac{1}{i!} \]

\(\text{Lemma 2}\)

集合 \(X = 1,\,2,\,\cdots,\,n\) 上恰有 \(k\) 个不动点的数量：

\[G_n^k = n!\left[1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!} + \cdots + \dfrac{(-1)^{n-k}}{(n-k)!}\right] = n! \cdot \sum_{i=0}^{n-k} (-1)^i \dfrac{1}{i!} \]

第一抽屉原理

将 \(m\) 件物品放进 \(n\) 个柜子里，则必有一个柜子至少有 \(\left[\dfrac{m-1}{n}\right] +1\) 个物品。

\(\text{Lemma}\)

将 \((\sum_{i=1}^n m_i)+1\) 件物品放入 \(n\) 个柜子里，则或者第一个抽屉里有至少 \(m_1+1\) 个物品，或者第二个柜子有至少 \(m_2+1\) 个物品……或者第 \(n\) 个柜子有至少 \(m_n +1\) 个物品。

第二抽屉原理

将 \(m\) 件物品放进 \(n\) 个柜子里，则必有一个柜子至多有 \(\left[ \dfrac{m}{n} \right] + 1\) 个物品。

\(\text{Lemma}\)

将 \((\sum_{i=1}^n m_i)-1\) 个物品放进 \(n\) 个抽屉内，则或者第一个抽屉里有至少 \(m_1-1\) 个物品，或者第二个柜子有至少 \(m_2-1\) 个物品……或者第 \(n\) 个柜子有至少 \(m_n -1\) 个物品。

Ramsey 定理

\(2\) 色完全图 \(K_6\) 中必然存在同色三角形。

平均值原理

设 \(a_1,\,a_2,\,\cdots,\,a_n\) 为实数，\(A = \dfrac 1n \sum_{i=1}^n a_i\)，则 \(a_1,\,a_2,\,\cdots,\,a_n\) 中必有一个数不小于 \(A\)，也必有一个数不大于 \(A\)。
设 \(a_1,\,a_2,\,\cdots,\,a_n\) 为正实数，\(G = \sqrt[n]{\prod_{i=1}^n a_i}\)，则 \(a_1,\,a_2,\,\cdots,\,a_n\) 中必有一个数不小于 \(G\)，也必有一个数不大于 \(G\)。

二项式定理

二项式定理阐明了一个多项式的系数

\[(a+b)^n = \sum_{i=0}^n \dbinom{n}{i}a^{n-i}b^i \]

推广到多项式：

\[(\sum_{i=1}^t x_i)^n = \sum_{\text{满足 }M\subset \mathbb{N},\,\sum_{i=1}^t m_i = n} \left[\dbinom{n}{m_1\;m_2\;\cdots\;m_t} \prod_{j=1}^{t}x_j^{m_j}\right] \]