Enumerative Combinatorics 第一卷 1.3 节

OI

---

1.3 排列统计量：循环，逆序表，下降集，笛卡尔树，q 模拟

1.3.2 对「有 $c_i$ 个长为 $i$ 循环的置换」计数

$$n !=1^{c_{1}} c_{1} ! 2^{c_{2}} c_{2} ! \cdots n^{c_{n}} c_{n} !\left(\# \mathfrak{S}_{S}^{\boldsymbol{c}}\right)$$
组合证明：考虑将置换写成循环组合的标准形式（长度非减）。括号内可以 shift，长度相同的循环可以任意交换。发现任意排列都能唯一表示，是一个双射。

1.3.9 排列与其逆序表的双射

$$\begin{aligned} \mathscr{T}_{n} &=\left\{\left(a_{1}, \ldots, a_{n}\right): 0 \leq a_{i} \leq n-i\right\} \\ &=[0, n-1] \times[0, n-2] \times \cdots \times[0,0] \end{aligned}$$

将排列映射到它的逆序表的映射 $I: \mathfrak{S}_{n} \rightarrow \mathscr{T}_{n}$ 是一个双射。

1.3.10 排列的逆序到阶乘的 $q$ 模拟

$$\begin{aligned} \sum_{\pi \in \mathfrak{S}_{n}} q^{i(\pi)} &=\sum_{a_{1}=0}^{n-1} \sum_{a_{2}=0}^{n-2} \cdots \sum_{a_{n}=0}^{0} q^{a_{1}+\cdots+a_{n}} \\ &=\left(\sum_{a_{1}=0}^{n-1} q^{a_{1}}\right)\left(\sum_{a_{2}=0}^{n-2} q^{a_{2}}\right) \cdots\left(\sum_{a_{n}=0} q^{a_{n}}\right) \end{aligned}$$

其中 $i(\pi)$ 表示排列 $\pi$ 的逆序数。上式也即 $[n]_q!$。

1.3.11 下降集与欧拉数初步

定义 $D(\pi)$ 为 $D(\pi)=\left\{i: a_{i}>a_{i+1}\right\}$，以及

$$\begin{array}{l}\alpha(S)=\operatorname{card}\left\{\pi \in \mathfrak{S}_{n}: D(\pi) \subseteq S\right\} \\ \beta(S)=\operatorname{card}\left\{\pi \in \mathfrak{S}_{n}: D(\pi)=S\right\}\end{array} \Rightarrow \alpha(S)=\sum_{T \subseteq S} \beta(T)$$
显然 $\alpha(S)$ 容易通过组合数计算。定义 $A_{n}(x)=\sum_{\pi \in \mathcal{S}_{n}} x^{1+d(\pi)}$ 为 Euler 多项式，用 $A(n,k)$ 表示其 $x^k$ 的系数，即有多少「长为 $n$ 且下降数为 $k-1$ 的排列」。

1.3.12 欧拉数与胜位数

考虑将排列写成标准形式，$a_{1}, a_{i_{1}+1}, \dots, a_{i_{k-1}+1}$ 是他们所在环里的最大元，按照 $a_{i_k}+1$ 升序排列。

$$\pi=\left(a_{1} a_{2} \cdots a_{i_{1}}\right)\left(a_{i_{1}+1} a_{i_{1}+2} \cdots a_{i_{2}}\right) \cdots\left(a_{i_{k-1}+1} a_{i_{k-1}+2} \cdots a_{n}\right)$$
显然有 $a_i \le a_i+1$ 或 $i=n$ 当且仅当 $\pi(a_i) \ge a_i$（称为一个弱胜位）。
$$n-d(\hat{\pi})=\#\{i \in[n]: \pi(i) \geq i\}$$
可以得到 结论：$A(n,k+1)$ 等于具有 $k$ 个胜位（严格大于）的排列数量。

1.3.14 排列与笛卡尔树（递增二叉树）

每次取出根之后两边递归，可以得到排列到笛卡尔树的映射 $\pi \mapsto T(\pi)$。性质：根据 $a_i$ 与 $a_{i-1},a_{i+1}$ 之间的大小关系（上升，下降，峰值，谷值），对应 $a_i$ 是否存在左右子树。

• 恰有 $k$ 个节点仅有左子树的笛卡尔树个数为 $A(n,k+1)$。
• 每个节点度数为 $0$ 或 $2$ 的笛卡尔树个数为交错排列的个数。

1.3.16 排列与单调栈树(?)（无序递增树）

每个元素向左侧比 $a_i$ 小的位置最大的元素连边（根节点为 $0$）。同样可以得到类似的结论。

• 根节点有 $k$ 个后继的单调栈树的个数为 无符号第一类斯特林数 $c(n,k)$。
• 具有 $k$ 个叶子的无序递增树的个数为 $A(n,k)$。

1.3.17 重集的逆序对与 q 二项式系数（Gauss 多项式）

$$\sum_{\pi \in \mathfrak{S}(M)} q^{i(\pi)}=\left(\begin{array}{c}\boldsymbol{n} \\ \boldsymbol{a}_{1}, \ldots, \boldsymbol{a}_{\boldsymbol{m}}\end{array}\right)$$

其中 $M = \{1^{a_1},\cdots,m^{a_m}\}$，后者实际上是关于 $q$ 的多项式。只需注意到下式

$$\left(\begin{array}{l}\boldsymbol n \\ \boldsymbol k\end{array}\right)=\left(\begin{array}{c} \boldsymbol {n-1} \\ \boldsymbol k\end{array}\right)+q^{n-k}\left(\begin{array}{l} \boldsymbol{n-1} \\ \boldsymbol{k-1}\end{array}\right)$$

1.3.18 对「$q$ 元有限域的 $n$ 维向量空间的 $k$ 维子空间」计数

所有 $q$ 元有限域均同构。考虑从 $V_n(q)$ 中选取有序的 $k$ 元无关向量组：

• 如果直接选择，那么有 $N = \prod (q^n-q^i)$。
• 或者先在 $G(n,k)$ 个子空间选择，$N=G(n,k)\prod(q^k-q^i)$。

可以得到 $G(n,k) = \binom {\boldsymbol n} {\boldsymbol k}$。

1.3.19 拆分，网格路径，q 二项式系数

令 $p(j, k, n)$ 为 $n$ 最多有 $k$ 个部分，最大部分 $\le j$ 的拆分个数。实际上也对应了从 $(0,0)$ 走向 $(j,k)$ 下方面积为 $n$ 的方案数。显然有

$$\sum_{n>0} p(j, k, n) q^{n}=\left(\begin{array}{c}\boldsymbol {j+k} \\ \boldsymbol j\end{array}\right)$$