# 组合数学学习笔记

# 排列

1. 不可重排列数

$n$ 个不同的物品选出 $m$ 个的排列数：$A_n^m = \frac{n!}{(n-m)!} \quad (n,m \in N^{*}, m \le n)$.

2. 可重排列数

$n$ 种物品选出 $k$ 个的排列数：$n^k$.

3. 圆排列

$n$ 个不同的物品选出 $m$ 个围成一个圆的排列数：$P_n^m = \frac{A_n^m}{m} = \frac{n!}{m \cdot (n-m)!}$.

4. 不尽相异元素全排列

$m$ 种物品共计 $n$ 件，第 $i$ 种物品有 $a_i$ 件，其全排列：$\frac{n!}{\prod\limits_{i = 1}^{m} {(a_i!)}}$.

5. 多重集的排列

在多重集中选 $n$ 件物品的排列数：$n!$ 除以指数型生成函数（指数型母函数）的 $n$ 次项的系数。

# 组合

1. 不可重组合数

$n$ 个不同的物品选出 $m$ 个的组合数：$C_n^m = \frac{n!}{m!(n-m)!}$.

2. 可重组合数

$n$ 中不同的物品选出 $m$ 个的组合数：$C_{n+m-1}^{n-1} = C_{n+m-1}^{m}$.

3. 不相邻的组合数

从 $n$ 个物品中选出 $m$ 个不相邻的物品的方案数：$C_{n-m+1}^{m}$.

4. 多重集的组合

在多重集中选 $n$ 件物品的组合数：普通型生成函数（普通型母函数）的 $n$ 次项系数。

5. 组合数常用公式

$C_{n}^{m} = C_{n}^{n-m}$
$C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}$
$C_{n}^{m+1} = C_{n}^{m} \cdot {\frac{n-m}{m+1}}$

6. Lucas 定理

$C(n, m) ~\%~ p = C(\lfloor\frac{n}{p}\rfloor,~\lfloor\frac{m}{p}\rfloor) ~\ast~ C(n \%p,~ m\%p) ~\%~ p$

# 公式 及 定理

1. 二项式定理

$(x+y)^n = \sum\limits_{i = 0}^n \binom{n}{i}{x^i} {y^{n-i}}$

2. 常见恒等式

$\sum\limits_{i = 0}^{n} \binom{n}{i} = 2^n$
$\sum\limits_{i = 0}^{n} (-1)^i \binom{n}{i} = 0$
$\sum\limits_{i = 0}^{n} 2^i \binom{n}{i} = 3^n$

3. 帕斯卡恒等式

$C_{n+1}^k = C_n^{k-1} + C_n^k$

4. Lucas 定理推论

$C_n^m$ 为奇数 $\Longleftrightarrow$ $n\&m = m$

5. 错排问题

$D_n = (n-1)(D_{n-1} + D_{n-2}) \quad (D_1 = 0, D_2 = 1)$
$D_n = n!\sum\limits_{i = 2}^{n} (-1)^i \frac{1}{i!}$
$D_n = \lfloor\frac{n!}{e} + 0.5\rfloor$

# 常见数列

# 斐波那契数列

1. 定义

$F_n$ = $F_{n-1} + F_{n-2} \quad (F_1 = 1, F_2 = 1)$

2. 通项公式

$f_n = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]$

3. 性质

平方与前后项：从第二项开始，每个奇数项的平方都比前后两项之积少 1，每个偶数项的平方都比前后两项之积多 1
前 $n$ 项的前缀和：$\operatorname{S}(n) = f_{n+2}-1$
奇数项求和：$\sum\limits_{i = 1} ^{n} f_{2n-1} = f_{2n}$
偶数项求和：$\sum\limits_{i = 1} ^{n} f_{2n} = f_{2n+1}-1$
平方求和：$\sum\limits_{i = 1} ^{n} f_{n}^2 = f_{n} \cdot {f_{n+1}}$

# 卡特兰数

1. 公式

$h(n) = \frac{C(2n,\, n)}{n+1} = C_{2n}^n - C_{2n}^{n-1}$
$h(n+1) = \sum\limits_{i = 0}^{n}h(i) \cdot h(n-i) \quad (h(0) = 1)$
$h(n+1) = \frac{4n+2}{n+2} \cdot h(n)$

2. 应用

$n$ 个数的出栈序列数。
$n$ 个结点的二叉树的种类数。
有 $n+1$ 个叶节点的满二叉树的个数。
在 $n \ast n$ 的格子的下三角走，每次向右或上走一格，走到右上角的方案数。
将凸多边形分割为三角形的方案数。
在圆上选 $2n$ 个点，是两两相连得到的 $n$ 条线段不相交的方案数。
左右括号各有 $n$ 个，组成的合法括号表达式的方案数。
. . . . . .

# 例题

组合数学的思想及实际应用更为重要

# P6475 [NOI Online #2 入门组] 建设城市

# 题目描述

(Building.)
要在灵水市建造 $2n$ 座并排的高楼 ，高度不可超过 $m$，前 $n$ 座不下降，后 $n$ 座不上升，指定编号为 $x$ 和 $y$ 的两栋高楼作为地标并使其高度相等，询问方案对 $998244353$ 取模后的结果（楼高是正整数）。

# Solution of The Problem

我们需要分类讨论，将地标建筑在 $n$ 的同侧与异侧分开考虑。
若在同侧，两地标及其中间建筑高度均相同，灵水市被分成 $3$ 个区间段， $[1, x)$, $(y, n]$, $[n+1, 2n]$, 枚举地标高度，计算贡献。
若在异侧，灵水市就被分成了 $4$ 部分， $[1, x)$， $(x, n]$， $[n+1，y)$， $(y, 2n]$，同样的枚举地标高度，计算贡献。
$n$ 座高楼的高度选择有 $m$ 种，建造的方案数等同于 $n$ 个相同的小球放入 $m$ 个不同的盒子里，盒子可空。
(Construction Complete)
(New Construction Options)

# P4921 [MtOI2018] 情侣？给我烧了！

# 题目描述

有 $n$ 对情侣去看电影，影院里有 $n$ 排座位，每排有 $2$ 个座位。
若一对情侣坐在了同一排，则称这一对情侣是和睦的。
那么问题是求出对于每一个 $k \in [1, n]$，和睦的情侣恰有 $k$ 对的方案数，两种方案不同当且仅当存在一个人在两种方案里坐了不同位置。

# Solution of The Problem

记 $f(x)$ 为有 $x$ 对情侣时，使他们均不和睦的方案数。
$Ans(n, k) = C_n^k \ast A_n^k \ast 2^k \ast f(n-k)$，表示从 $n$ 个人中选出 $k$ 个，再选出 $k$ 个座位让他们坐，而每对情侣又有两种坐法，且其余情侣均不和睦的方案数。
我们再来看 $f(x)$，考虑递推求解，假设已经有 $f(0)$ ~ $f(x-1)$ 的答案。
先在 $2x$ 人里面选出一人，再在剩下 $2(x-2)$ 人里选出一个不是他 cp 的人，方案数为 $2x(2x-2)$.
若让这两位的 cp 坐在一起，有 $n-1$ 排可以选择他们也可以互换位置，而且其他 $x-2$ 对情侣相互错开的方案数为 $f(x-2)$.
若让这两位的 cp 不坐在一起，将他们看做一对情侣 (大雾) ，和剩下的 $x-2$ 对情侣一起计算，方案数为 $f(x-1)$.
总的方案数就是 $f(x) = 4x(x-1) \cdot [f(x-1) + 2(x-1)f(x-2)]$.
于是我们就成功了。
(Construction Complete)