组合数学杂记

不是很感兴趣。

# 和积法则

# N 取 r 的可重组合数：

$$\begin{pmatrix}n+r-1\\r\end{pmatrix}$$

• 因为可以把可重结果，例如$1,1,1,2,2$，分别对应位置$+0,+1,+2,+3,+4$，然后映射到$1,2,3,5,6$。

• 于是 n 取 r 可重就转换成了 n+r-1 取 r 不可重。于是得到了答案。$+0,+1,...,+r-1$，所以从$1,...,n+r-1$ 中选$r$ 个后，再$-0,-1,-2,..,-r+1$ 就得到了一个答案。

• 注意这个问题转化是一一映射的，不能选择$+1,+2,+3,+4,+5$ 是因为存在方案$1,2,3,4,5$，他无法转化回去。

[例]：把 r 个相同的球，放入 n 个不同的箱子里，方案数是多少？

解：就是 n 取 r 的可重组合数。可以从 n 中取可重的 r 个盒子，再把这 r 个球放到对应的盒子中。

# 杂题

含数字 6，能被 3 整除的 5 位整数有多少个？

• 手动数位 dp，记$dp[i][j][0/1]$ 表示到第 i 位，模 3 余$j$，是否含 6。直接状态转移。

# 排列组合

# prufer 序列

一棵标号树和一个 prufer 序列是一一对应的。

• 树转化为 prufer 序列：
  • 将叶子结点中，最小标号的一个删除，序列中加入它的父亲。
  • 重复该过程直到树只剩下两个结点。
• prufer 序列转化为树：
  • 构造一个集合\
  • 找出集合中最小未在 prufer 序列中出现的数，将该数和 prufer 序列中第一个数连边
  • 把该数和 prufer 序列中第一个数删除。
  • 重复 n-2 次，把集合中剩余的两个点连边。

例：

它的 prufer 序列为$\{3,5,1,3\}$。由 prufer 序列构造树时，连边顺序为$(2,3),(4,5),(1,5),(1,3),(3,6)$。

# 杂题

从 1~300 中取 3 个不同的数，其和能被 3 整除，有多少种取法？

• 分组：

  $$\{1,4,7,...,298\}\\ \{2,5,8,...,299\}\\ \{3,6,9,...,300\}$$

  只能三个都取同一组，或 3=0+1+2 每个组各取一个。于是答案是$3C_{100}^3+100^3$。

m 个人从 n 个入口进站，只考虑同一个入口进站人的先后顺序，不考虑不同入口进站的先后顺序。求进站顺序方案数。

• 强行整了个插板法例题… 相当于 m 个人插 n-1 个板隔开，还要考虑全排列。

  答案是$\frac{(m+n-1)!}{(n-1)!}$，即把 m 个人和 n-1 个板都当作元素全排列，然后板是等价的，所以除去$(n-1)!$。

$x_1+x_2+...+x_n=r$，其中$x_1,x_2,...,x_n\geq 1$，都是整数。求解的个数。

• 这种也是插板法，答案为$C_{r-1}^{n-1}$。即把$1,1,...,1$（r 个 1）插$n-1$ 个板，分成 n 份。

$x_1+x_2+...+x_n=r$，其中$x_1,x_2,...,x_n\geq 0$，都是整数。求解的个数。

• 转化成$(x_1+1)+(x_2+1)+...+(x_n+1)=r+n,(x_1+1),...,(x_n+1)\geq 1$。答案就是$C_{n+r-1}^{n-1}$。

n 个 0，n 个 1，组成一个 2n 位二进制数。要求从左到右扫描，使得 1 的个数总是不小于 0，求方案数。

• 其实就是 n 对括号合法匹配数。对于一个合法串，可以考虑其最后一个括号的匹配情况，即它一定满足形式：

  $$P=A(B)$$

  而$A,B$ 都是合法的子串。所以 P 的方案数就是$P(n)=\sum_{i=0}^{n-1}P(i)P(n-1-i)$。即 A 和 B 的子串长度可以是$0..2(n-1)$。

  这其实是卡特兰数的递推数列，即最终方案为$C_{2n}^n/(n+1)$。

# 排列的生成

# 字典序

对于一个排列$P_1P_2P_3...P_n$，求他下一个排列。

• 找到末尾最长降序子列：$P_{i+1}P_{i+2}...P_n$

• 记下$P_i$，找到比$P_i$ 大的最右面的一个数，记为$P_k$

• 交换$P_i,P_k$

• 把$P_k$ 右侧子列倒序排列。

例：$349687521$，$P_{i+1}...P_n=87521$，$P_i=6$，$P_k=7$

​ 所以下一个字典序为$349712568$。

康托编码：记$a_i$ 为$P_i$ 右侧比$P_i$ 小的数字个数。则排列$P_1P_2P_3...P_n$ 可一一映射为其字典序排名：

$$d=a_1(n-1)!+a_2(n-2)!+...+a_{n-1}1!$$

注：$d=0,1,...,n!-1$

根据排列计算其字典序数是简单的。同样也可以求第 k 个排列。以$n=5$，求第$95$ 个排列为例：

• $95/4!=3..........23$（带余除法）
• $23/3!=3..........5$
• $5/2!=2..........1$
• $1/1!=1.........0$

于是第一位为$4$（右边肯定有 3 个比他小），第二位为 5（右边有三个比他小，其中 4 在他左侧），第三位为 3（右边肯定有两个比他小），第四位为 2，第五位为 1。

所以第 95 个排列为 45321。（注意从 0 开始数）

# 序数法

将一个排列$P_1P_2...P_n$ 一一映射到一个序列$a_{n-1}a_{n-2}...a_1$。其中，$a_i$ 表示序列中，$i+1$ 右侧比$i+1$ 小的数的个数。

例如：$349687521$ 对应的序数为$64332221$。显然，序列的范围是$00...0$ 到$(n-1)(n-2)...1$，共$n!$ 个。

• 求下一个排列：序数加一。序数的$a_1$ 是 2 进制，$a_2$ 是 3 进制，$a_3$ 是 4 进制，以此类推。

  因此，序数$64332221+1=64332300$。

  而序数转化为排列是简单的。从大到小依次找到数应该在的位置就好了。$64332300$ 对应的排列就是$419687523$。

# 容斥原理

$$|\bigcup_{i=1}^n A_i|=\sum_{i=1}^n|A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-....+(-1)^n|A_1\cap A_2\cap A_3\cap....\cap A_n|\\ |\bigcap_{i=1}^n\bar{A_i}|=|U|-|\bigcup_{i=1}^n A_i|$$

# 错排

答案是：

$$n!-C_n^1(n-1)!+C_n^2(n-2)!-C_n^3(n-3)!+...+(-1)^kC_n^k(n-k)!+(-1)^nC_n^n0!\\ =n!-\frac{n!}{1!}+\frac{n!}{2!}-....+(-1)^k\frac{n!}{k!}+...+(-1)^n\frac{n!}{n!}\\ =n!(1-\frac{1}{1!}+\frac{1}{2!}-...+(-1)^n\frac{1}{n!})$$

• 记$A_i$ 为数字 i 在自己位置上。答案就是$|\bigcap_{i=1}^n \bar{A_i}|$。而:

  $$\sum_{i_1 < i_2<...<i_t}|A_{i_1}\cap A_{i_2}\cap...\cap A_{i_t}|=C_n^t(n-t)!$$

  左式的理解可以为：“存在（至少）t 个数字不在自己位置上的方案数”。

# 欧拉公式

$n=p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n}$。记$[1,n]$ 中，$p_i$ 的倍数集合为$A_i$，则$|A_i|=\frac{n}{p_i},|A_i\cap A_j|=\frac{n}{p_ip_j}$。于是比 n 小和 n 互质的数的个数就为$|\bigcap_{i=1}^n\bar{A_i}|$。

# 杂题

m 个元素的集合，到 n 个集合满射的个数为$n^m-C_n^1(n-1)^m+C_n^2(n-2)^m-...+(-1)^{n-1}C_n^{n-1}1^m$

• 记$A_i$ 为第 i 个元素没有原象的方案。答案就是$|\bigcap_{i=1}^n\bar{A_i}|$。而:

  $$\sum_{i_1 < i_2<...<i_t}|A_{i_1}\cap A_{i_2}\cap...\cap A_{i_t}|=C_n^t(n-t)^m$$

  左式的理解可以为：“存在（至少）t 个元素没有原象的方案数”。

# 鸽巢原理

# Ramsey 数

记$r(p,q)$ 为参数是$p,q$ 的 Ramsey 数。它的含义是，对任意$n>r(p,q)$，那么 n 个点的完全图，用两种颜色去边染色，要么存在$p$ 个顶点构成的子图的边全是一种颜色，要么存在$q$ 个顶点构成的子图的边全是另一种颜色。

即$n\geq r(p,q)$，要么存在 p 个人相互认识，要么存在 q 个人相互不认识。

# 杂题

参加一个宴会的人中，至少存在两人，它们认识的宴会上的人数相同。

• 考虑 n 个人参加，如果他们认识的人两两不同，则他们认识的人数从小到大排就是$0,1,2,...,n-1$（共 n 个），那么显然认识最多的人要认识剩下的所有人，而认识最少的人却一个人都不认识，这矛盾。

1 到 2n 的正整数中，任取 n+1 个，则它们中必有一对数，其中一个是另一个的倍数。

• 考虑所有的正整数都能写成$A*2^B$ 的形式，A 是奇数，B 是正整数。而很显然$[1,2n]$ 中的奇数只有 n 个，故取 n+1 个数肯定会有两个数对应的 A 相同。则它们之间有倍数关系。

设$a_1,a_2,...,a_m$ 是一个正整数序列，则存在$1\leq k\leq l\leq m$，使得$a_k+a_{k+1}+...+a_l$ 是 m 的倍数。

• 考虑前缀和模 m 的结果，记$S_n=\sum_{i=1}^n a_i\quad mod\; m$。若存在 n，使得$S_n=0$ 则直接得证。否则，$S_n$ 都不为 0，则它们为$1,2,...,m-1$，又因为有 m 个前缀和，所以肯定有两个前缀和相同。将它们相减，就得到了一段连续的模 m 为 0 的子序列。

设$a_1,a_2,...,a_n$ 是一组正整数序列，满足$a_1+a_2+...+a_n\leq r$。求证$\forall m<2n-r$，都存在一个子序列使得$a_h+a_{h+1}+...+a_{k-1}+a_k=m$。

• 考虑前缀和$S_n$，然后可以构造两组单调的正整数序列为$S_1,S_2,...,S_n$ 和$S_1+m,S_2+m,...,S_n+m$，共 2n 个数。显然这 2n 个数都小于等于$r+m$。如果$2n>r+m$，则必定存在两个数相等。而且一个数在前一个序列，另一个数在后一个序列。则存在$h,k$ 使得$S_h-S_k=m$。

$n^2+1$ 个不同实数组成的序列中，一定存在长为 n+1 的单调子序列。

• 记$f[i]$ 为从第 i 位开始最长严格递增的子序列长度。若$\forall 1\leq i\leq n^2+1$，都有$f[i]\leq n$ 的话，考虑抽屉原理，则至少有$f[i_1]=f[i_2]=...=f[i_n]=f[i_{n+1}]$。

  于是可以考虑$a_{i_1},a_{i_2},...,a_{i_n},a_{i_{n+1}}$。若它们单调减，则构成了一个长为$n+1$ 的单调减序列。否则，若存在$a_{i_1}<a_{i_2}$，则$f[i_1]> f[i_2]$，矛盾。

六个点的完全图中，用红 / 黑给边染色，必然存在同色三角形。

• 考虑点 A 连的五条边，根据抽屉原理，至少有三条边是同色的，不妨设为$AB,AC,AD$。再考虑边$BC,BD,CD$，若它们中有一条是和$AB,AC,AD$ 同色，则存在了同色三角形。否则，它们都是另一种颜色，则$BCD$ 就是一个同色三角形。

# 生成函数

# 普通生成函数

求解多重递推可以这样，例如：

$$\begin{cases}a_n=9a_{n-1}+b_{n-1}\\ b_n=9b_{n-1}+a_{n-1} \end{cases}\\ a_1=8,b_1=1$$

不妨设数列的生成函数分别是$A(x),B(x)$：

$$A(x)=a_1+a_2x+a_3x^2+...\\ B(x)=b_1+b_2x+b_3x^2+...$$

然后可以凑出递推式：

$$a_n-9a_{n-1}-b_{n-1}=0\\ \begin{cases}A(x)=a_1+a_2x+a_3x^2+...\\ -9xA(x)=-9a_1x-9a_2x^2-...\\ -xB(x)=-b_1x-b_2x^2-...\\ \end{cases}\\ \therefore (1-9x)A(x)-xB(x)=a_1+(a_2-9a_1-b_1)x+(a_3-9a_2-b_2)x^2+....\\ =a_1+0+0+0+...\\ =8$$

同理，由第二个递推式有$(1-9x)B(x)-xA(x)=b_1=1$。所以可以解方程，得：

$$A(x)=\frac{-71x+8}{(1-8x)(1-10x)}\\ B(x)=\frac{-x+1}{(1-8x)(1-10x)}$$

# 指数生成函数

例如错排问题：

$$D_n-nD_{n-1}=(-1)^n\\ D_0=1,D_1=0,D_2=1$$

可以设指数型生成函数：

$$G(x)=D_0+D_1x+\frac{D_2}{2!}x^2+\frac{D_3}{3!}x^3+...\\ xG(x)=D_0x+D_1x^2+\frac{D_2}{2!}x^3+\frac{D_3}{3!}x^4+...\\ \therefore (1-x)G(x)=D_0+\sum_{i=1}^{\infin}(\frac{D_i}{i!}-\frac{D_{i-1}}{(i-1)!})\\ \because \frac{D_n}{n!}-\frac{D_{n-1}}{(n-1)!}=\frac{(-1)^n}{n!}\\ \therefore (1-x)G(x)=D_0+\sum_{i=1}^{\infin}\frac{(-x)^i}{i!}=1-\frac{x}{1!}+\frac{x^2}{2!}-...=e^{-x}\\ \therefore G(x)=\frac{e^{-x}}{1-x}=(1-\frac{x}{1!}+\frac{x^2}{2!}-...)(1+x+x^2+x^3+...)\\ \therefore \frac{D_n}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-....+\frac{(-1)^n}{n!}$$

其中，$\frac{D_n}{n!}$ 就是$x^n$ 前的系数。考虑多项式乘法。

# 整数拆分问题

将 n 拆成 1，2，4，5 的和，不允许重复。

• $(1+x)(1+x^2)(1+x^4)(1+x^5)$ 中，$x^n$ 前的系数

将 n 拆成 1，2，4，5 的和，允许重复。

• $(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^4+x^8+x^{12}+...)(1+x^5+x^{10}+...)$

# 棋盘多项式

棋盘是由若干格子组成的。格子间不一定相连，但每个格子都有两个属性：行和列。行和列都是整数。格子里可以放棋子。

记$r_k(C)$ 表示在棋盘 C 中放 k 个棋子的方案数，要求同一行、同一列至多一个棋子。

那么$R(C)=\sum_{i=1}^nr_i(C)x^i$ 称为棋盘 C 的棋盘多项式。

例：

# 性质

• 对于一个棋盘 C，对于任意一个格子 x，记 C 去掉 x 这一格子后的剩余棋盘是$C_e$，记 C 去掉 x 所在行和列所有的格子后的剩余棋盘为$C_i$，则有：

$$r_k(C)=r_{k-1}(C_i)+r_k(C_e)\\ R(C)=xR(C_i)+R(C_e)$$

​ 原理就是，要么格子 x 里有棋子，即$r_{k-1}C_i$，要么格子 x 里没棋子，即$r_k(C_e)$。

• 若对于一个棋盘 C，它是由两部分$C_1,C_2$ 组成的，且$C_1$ 和$C_2$ 中的行列都没有交集。则有：

  $$r_k(C)=\sum_{i=0}^kr_i(C_1)r_{k-i}(C_2)\\ R(C)=R(C_1)R(C_2)$$

  例：

# 应用 —— 有禁区的方棋盘放棋子方案数

一个$n\times n$ 的方格棋盘，其中有一些禁区。则在其中放 n 个棋子（不许同一行同一列有多个棋子）的方案数为：

$$n!-r_1(C)(n-1)!+r_2(C)(n-2)!+...+(-1)^nr_n(C)$$

其中，$r_k(C)$ 表示在禁区棋盘放 k 个棋子的方案数。例：

证明：

设$A_i$ 为第 i 行的那个棋子落入禁区的放置方案数。则答案是$|\bigcap_{i=1}^n\bar{A_i}|$。

而$\sum_{i=1}^n|A_i|=r_1(C)(n-1)!,\sum_{i<j}|A_i\cap A_j|=r_2(C)(n-2)!$。于是由容斥原理可以得出。

# 应用 —— 错排

• n 的错排数为，$n\times n$ 的棋盘，禁区为对角线，求方案数。显然，禁区棋盘的多项式为$R(C)=(1+x)^n=1+C_n^1x+...$。
• 所以方案数为$n!-C_n^1(n-1)!+C_n^2(n-2)!-...+(-1)^nC_n^n$。

# 莫比乌斯反演

$$F(n)=\sum_{d|n}f(d)\\ f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\\ \mu(x)=\begin{cases}1&x=1\\ (-1)^n&x=p_1\cdot p_2\cdot p_3\cdot....\cdot p_n\\ 0&else \end{cases}$$

其中，$p_1,p_2,...,p_n$ 是互不相同的素数。

莫比乌斯反演的证明就是：

$$\sum_{d|n}\mu(d)=\begin{cases}1&n=1\\0&else\end{cases}\\ \sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\sum_{d_1|\frac{n}{d}}\mu(d)f(d_1)=\sum_{d_1|n}f(d_1)\sum_{d|\frac{n}{d_1}}\mu(d)=f(n)$$

# Burnside 定理和 Polya 定理

# Burnside 定理

考虑计数问题。用两种颜色去染$2\times 2$ 的棋盘，旋转相同算一种。求方案数。

首先，要画出左右可能的染色方案，即$2^4=16$ 种。如下图：

按行优先，我们把这些方案数记为 1，2，…，16。然后我们需要去重。

• 旋转$0$°，则考虑这些染色方案间的等价置换关系。置换为$p=(1)(2)(3)...(16)$。意思是，第 i 个方案在旋转 0° 后就是第 i 个方案。
• 逆时针旋转 90°，则置换为$p=(1)(2)(3456)(78910)(11\;12)(13\;14\;15\;16)$。意思是，第 1 个方案逆时针转 90° 后还是第 1 个，第 3 个方案逆时针 90° 后是第 4 个方案…
• 顺时针旋转 90°，则置换为$p=(1)(2)(6543)(10\;987)(11\;12)(16\;15\;14\;13)$
• 旋转 180°，置换为$p=(1)(2)(3\;5)(4\;6)(7\;9)(8\;10)(11)(12)(13\;15)(14\;16)$。

然后去重方案数就是每个置换中长度为 1 的置换数的平均。即：

$$\frac{16+2+2+4}{4}=6$$

最后答案是 6 种。

# Polya 定理

显然 Burnside 定理要画出所有的方案数，这不太好。考虑 polya 定理。同样一个问题，对棋盘入手：

然后显然，棋盘有 4 个元素。

• 旋转 0°，棋盘元素的置换为$p=(1)(2)(3)(4)$

• 逆时针旋转 90°，棋盘元素的置换为$p=(4321)$。4 号到 3 号位置上，3 号到 2 号位置上…

• 顺时针旋转 90°，棋盘元素的置换为$p=(1234)$。

• 旋转 180°，棋盘元素的置换为$p=(13)(24)$。

然后统计的方案数就是$\frac{2^4+2^1+2^1+2^2}{4}=6$，即考虑 “染色数 ^ 置换节数” 的平均值。（置换由几个小置换乘积而成）

# 有重复元素的圆排列

从 1，2，3，4 种，取 4 个数出来（可以重复）。将取出来的数排成一个圆排列（旋转相同算一种），则方案数有多少？

• 首先定义一个圆排列的周期。考虑一个圆排列：(1 2 1 2)，它的周期是 2（想象成一个圆）。

  圆排列 (1 2 3 1) 的周期为 4，(1 1 1 1) 的周期为 1。

  即周期就是最小循环节长度。

• 然后要求的答案就是$\sum_{d|n}M(d)$，其中$M(d)$ 表示周期为 d 的圆排列方案数。

  显然有$\sum_{d|n}M(d)\times d=m^n$，所有的方案数就是每个周期为 d 的方案数再乘上它的周期。

  莫比乌斯反演，有：

  $$nM(n)=\sum_{d|n}m^d\mu(\frac{n}{d})=\sum_{d|n}\mu(d)m^{\frac{n}{d}}\\ \therefore M(d)=\frac{1}{d}\sum_{d_1|d}\mu(d_1)m^{\frac{d}{d_1}}$$

  所以最后的答案就是：

  $$M(1)=4\mu(1)=4\\ M(2)=\frac{1}{2}(\mu(1)4^2+\mu(2)4^1)=6\\ M(4)=\frac{1}{4}(\mu(1)4^4+\mu(2)4^2+\mu(4)4^1)=60\\ \therefore ans=4+6+60=70$$

# 卡特兰数

$$C_n=\frac{C_{2n}^n}{n+1}\\ C_n=\sum_{i=0}^{n-1}C_iC_{n-i-1}$$

应用：

• n 边凸多边形，划分成若干三角形的方案数。
• 以 1，2，…，n 的顺序入栈，不同出栈结果的方案数。
• n 对括号合法匹配串数。
• n 个结点的二叉树的不同形态数。