前言
本文引入了组合统计量的概念，并探讨了其在序列上、格路径上的相关内容，并着重介绍了停车问题可解序列的集合 (Parking Function) 相关的定理及其与有标号有根森林 (Rooted labeled forests) 间的双射。
目录
- 格路径的基本概念
-
- 判定
- $\rm Parking$ 函数到 $\rm Dyck$ 路的映射
- $\rm Parking$ 函数的计数
-
- $q\text -$模拟
- 排列上的组合统计量
- 格路径的组合统计量
-
- 有标号森林的基本概念
- $\mathcal{PF}_n$ 与 $\mathcal F_n$ 的几个关联
- 停车问题与树的双射
- 映射 $\varphi:\mathcal {F_n}\to\mathcal{PF}_n
- 逆映射：\varphi^{-1}:\mathcal{PF}_n\to\mathcal{F}_n
格路径的基本概念
我们首先对格路径作一个基本介绍，作为后文与之相关内容的一个铺垫，并稍微探讨其计数问题。
卡特兰数与 Dyck 路
从 (0,0) 走到 (p,q) 的格路径为 \binom{p+q}{p}=\binom{p+q}{q}。现在考虑从 (0,0) 至 (p,q) 的下对角线格路径数量，我们可以将起点和终点各下移一格，将问题转化为求 (0,-1)\to(p,q-1) 的总路径数量减去触碰或穿过对角线的路径数量。显然，这样的路径能与 (-1,0)\to(p,q-1) 一一对应。
因之从 (0,0) 至 (p,q) 的不穿过对角线的格路径数量为：
\binom{p+q}{q}-\binom{p+1+q-1}{q-1}=\frac{p-q+1}{p+1}\binom{p+q}{q}
令 p=q=n，我们就得到了卡特兰数 C：
C_n=\frac{1}{n+1}\binom{2n}{n}
相仿地，一条不走到对角线下方的格路径称作 \mathbf{Dyck} 路。所有 n 阶 \mathrm{Dyck} 路的集合记作 \mathcal D_n。
Delannoy 数
现在考虑不仅能水平、垂直前进，还可以沿右上对角线走一格（\rm HVD 路径）时，从 (0,0) 到 (p,q) 的路径数。这个数就是 \mathbf{Delannoy} 数。
如果使用了 r 个对角步，那么剩下 p-r,q-r 个垂直和水平步。设:
D(p,q:r)=\binom{p+q-r}{p-r\quad q-r\quad r}
则 \rm Delannoy 数 D(n,m) 为：
D(n,m)=\sum_{k=0}^{\min(n,m)}\binom{n+m-k}{n-k\quad m-k\quad k}=\sum_{k=0}^{\min(n,m)}\frac{(n+m-k)!}{(n-k)!(m-k)!k!}
递推关系
考虑 C_n 的计数意义。我们枚举第一次碰到主对角线的 k，使 (0,0)\to(k,k) 且中间不经过下对角线，即 C_{k-1}。而 (k,k)\to(n,n) 就是 C_{n-k}。从而：
C_n=\sum_{k=1}^n C_{k-1}C_{n-k}=\sum_{k=0}^{n-1}C_{k}C_{n-k-1}
即：
C_{n+1}=\sum_{k=0}^nC_kC_{n-k}
设 C(z)=\sum\limits_{k=0}^{\infty}C_kz^k 为卡特兰数列的生成函数，于是就有：
\begin{aligned}
C^2(z)&=\sum_{s=0}^\infty\left(\sum_{k=0}^s C_kC_{s-k}\right)z^s=\sum_{k=0}^{\infty}C_{k+1}z^k\\&
=\frac{1}{z}\sum_{k=0}^\infty C_{k+1}z^{k+1}=\frac{C(z)-1}{z}
\end{aligned}
解出有意义的解为：
C(z)=\frac{1-\sqrt{1-4z}}{2z}
C(z) 的展开
\begin{aligned}
C(z)&=\frac{1-\sqrt{1-4z}}{2z}=\frac{1}{2z}\left(1-(1-4z)^\frac{1}{2}\right)\\
&=\frac{1}{2z}\left(1-\sum_{i=0}^{\infty}\binom{\frac{1}{2}}{i}(-4z)^i\right)
\end{aligned}
从而：
\begin{aligned}
C_n&=\left[z^n\right]C(z)=\frac{1}{2}\binom{\frac{1}{2}}{n+1}(-1)^n4^{n+1}\\
&=\frac{1}{2}\frac{\prod_{k=0}^n\left(\frac{1}{2}-k\right)}{(n+1)!}(-1)^n4^{n+1}\\
&=\frac{1}{2}\frac{\frac{1}{2}\prod_{k=1}^n\left(k-\frac{1}{2}\right)}{(n+1)!}4^{n+1}\\
&=\frac{1}{2}\frac{(2n)!}{2^nn!(n+1)!}2^{n+1}=\frac{(2n)!}{n!(n+1)!}\\
&=\frac{1}{n+1}\binom{2n}{n}
\end{aligned}
左右子树地位不等同的二叉树计数
有两种方法可以得到其二叉树的生成函数。我们设 $\mathcal {A,B}$ 表可空和不可空的左右不等同二叉树组合类，那么有：
$$
\mathcal A=\epsilon+\mathcal A{\times}{\circ}{\times}\mathcal A
$$
$$
B=\circ+\mathcal B{\times}{\circ}+{\circ}{\times}\mathcal B+\mathcal B{\times}{\circ}{\times}\mathcal B
$$
可解得：
$$
A(z)=\frac{1-\sqrt{1-4z}}{2z},\quad B(z)=\frac{1-2z-\sqrt{1-4z}}{2z}
$$
的确满足 $\mathcal A=\epsilon+\mathcal B$；这两种途径都得到了卡特兰数。事实上我们还可以代入其生成函数验证 $\mathcal A$ 和 $\mathcal B$ 的如下关系：
$$
\mathcal A=\epsilon+\circ+\mathcal B{\times}{\circ}+{\circ}{\times}\mathcal B+\mathcal B{\times}{\circ}{\times}\mathcal B
$$
## Schröder 数
设 $(0,0)\to(p,q)$ 的下对角 $\rm HVD$ 路径的计数为 $R(p,q)$，并记 $R(p,q:r)$ 表示使用了 $r$ 个 $\rm D$ 移动的不穿过对角的路径。
除去 $r$ 个 $\rm D$ 路径后，剩下 $(p-r,q-r)$ 就是一个不穿过对角线上方的路径计数。然后将 $r$ 插入到 $\rm H,V$ 和两端的中间，总方案数为 $\binom{p+q-r}{r}$。简单计算可得：
$$
R(n,m)=\sum_{k=0}^{\min(n,m)}R(n,m:k)
$$
$$
=\sum_{k=0}^{\min(n,m)}\frac{n-m+1}{n-k+1}\frac{(n+m-k)!}{(n-k)!(m-k)!k!}
$$
**$\mathbf{ Schröder}$ 数** $R_n$ 定义为 $R(n,n)$：
$$
R_n=\sum_{k=0}^n\frac{1}{n-k+1}\frac{(2n-k)!}{k!((n-k)!)^2}
$$
所有 $n$ 阶 $\rm HVD$ 格路径的集合记作 $\mathcal S_n$。
### 生成函数
考虑从 $(0,0)\to (n,n)$ 的第一步。当这一步为 $(1,1)$ 时，此后的路径数目即为 $R_{n-1}$。而当第一步为 $(1,0)$ 时，我们总能找到一个 $1\leqslant k\leqslant n$ 的 $k$，使得 $k$ 是第一个碰到对角线的点。在 $k$ 前的路径个数是 $R_{k-1}$，$k$ 以后为 $R_{n-k}$。综合以上两类第一步的数量可得：
$$
R_n=R_{n-1}+\sum_{k=1}^nR_{k-1}R_{n-k}=R_{n-1}+\sum_{k=0}^{n-1}R_kR_{n-1-k}
$$
其中 $R_0=1$。从而：
$$
z^nR_n=z\left(z^{n-1}R_{n-2}\right)+z\left(\sum_{k=0k}^{n-1}z^kR_{k}z^{n-1-k}R_{n-1-k}\right)\quad(n\geqslant 1)
$$
令 $R(z)$ 为 $\rm Schröder$ 数的生成函数，因 $R_0=1$，故有：
$$
R(z)=1+zR(z)+zR^2(z)
$$
解出有意义的解为：
$$
R(z)=\frac{1-z-\sqrt{z^2-6z+1}}{2z}
$$
# Parking 函数的基本概念
**$n$ 元 $\mathbf{Parking}$ 函数** 定义为一个使 $n$ 位停车问题可解的序列 $P=a_1a_2\dots a_n$。所有 $n$ 元 $\mathrm{Parking}$ 函数的集合记作 $\mathcal{PF}_n$。
### 停车问题
有 $n$ 个停车位和 $n$ 辆车，每辆车 $i$ 有一个偏好的停车位置 $a_i$。每辆车依次进入时，首先开到位置 $a_i$。若该位置有车，则在该车位沿往后最近的一个空位停车，求序列 $a_i$ 使得每辆车均可以停车成功。该问题称为**停车问题**。
## 判定
**定理**$\quad$序列 $a_1a_2a_3\dots a_n$ 是 $\rm Parking$ 函数，当且仅当 $a$ 重排后的序列 $b_1b_2\dots b_n$ 满足 $\forall i,b_i\leqslant i$。
$Proof.\quad$该判定等价于偏好 $1\sim i$ 的车大于等于 $i$ 辆。将 $n$ 个车位后面再加一个车位，并将 $n+1$ 个车位首尾接成一个环，则条件等价于位置 $n+1$ 无车停。
- 充分性：假设满足该判定且位置 $n+1$ 有车，则必有一个 $i\leqslant n$ 无车。则此时偏好 $1\sim i$ 的车仅有 $i-1$ 辆，矛盾。
- 必要性：位置 $n+1$ 无车，表明对于任意 $i\leqslant n$，位置 $1$ 至 $i$ 均停满车，即 $b_i\leqslant i$。
这就证明了该定理。$\square
推论\quad一个 \text{Parking} 函数的所有排列仍是 \rm Parking 函数。
Parking 函数到 Dyck 路的映射
考虑一个 \mathrm{Dyck} 路。将每辆汽车放在一个垂直步的正右一格位置，且限制若 i 在 j 的上方，则要求 i>j。
这样放置的意义为：若列 i 上放置了车 i_1,\dots,i_j，则表明这些车以位置 i 为最喜欢的车位。\rm Parking 函数的要求暗含了 \mathrm{Dyck} 路的要求，即，它满足了上述判定。
如果你不理解，请看下面这个例子。4 辆车的偏好位置分别为 a_1=2,a_2=3,a_3=1,a_4=2，对应第一列上放置数字 3，第二列上放置数字 1,4，第三列上放置数字 2。\rm Dyck 路不穿过主对角线的限制使这种放置满足了 a 重排后 b_i\leqslant i 的要求。
Parking 函数的计数
$$
(n+1)^{n-1}
$$
$Proof.\quad$下面记 $[n]=\{1,2,\dots,n\}$。考虑对上述环形停车问题稍作改变，即 $a_i\in[n+1]$。易见这个改变不影响成为 $\rm Parking$ 函数的条件，即，我们仍然需要对使得车位 $n+1$ 空出的序列进行计数。所有满足 $i\in[n],a_i\in[n+1]$ 的序列共有 $(n+1)^n$ 个，且每个序列必空出一个位置。由圆周的对称性，空出车位 $n+1$ 的数列数量，即 $n$ 元 $\rm Parking$ 函数的数量 $|\mathcal{PF}_n|$ 为 $(n+1)^{n-1}$。$\square
q\text -模拟与组合统计量
一个组合统计量是一个组合类 \mathcal A 到自然数集的具有组合意义的映射 f:\mathcal A\to \mathbb{N}。
q\text -模拟
一个非负整数 n 的 \mathbf q\text -模拟 是一个关于 q 的 n-1 次多项式，记作 [n]_q，其为：
[n]_q=1+q+\dots+q^{n-1}
定义：
[n]!=[1]_q[2]_q\cdots[n]_q\,,\quad\begin{bmatrix}n\\k\end{bmatrix}_q=\frac{[n]!}{[k]![n-k]!}
为 \mathbf{q}-阶乘和 \mathbf{q}-二项式系数。显然 \lim_{q\to1}\begin{bmatrix}n\\k\end{bmatrix}_q(q)=\dbinom{n}{k}。更一般地：
\begin{bmatrix}n\\m_1\quad m_2\quad \cdots\quad m_k\end{bmatrix}_q=\frac{[n]!}{[m_1]![m_2]!\cdots[m_k]!}
为 \mathbf{q}-多项式系数。
q\text -帕斯卡公式
\begin{bmatrix}n\\k\end{bmatrix}_q=q^{k-1}\begin{bmatrix}n-1\\k\end{bmatrix}_q+\begin{bmatrix}n-1\\k-1\end{bmatrix}_q
排列上的组合统计量
定理（Mahonian 性质）
定义 \mathcal P_n 为 [n] 上所有长度为 n 的无重复序列的集合，设 w\in\mathcal P_n，定义组合统计量 \operatorname{maj},\operatorname{inv} 为：
\operatorname{inv(w)}=\sum_{i<j,w_i>w_j}1\,,\quad\operatorname{maj(w)}=\sum_{w_i>w_{i+1}}i
则对于 \rm maj,inv，其具有 \rm Mahonian 性质：
\sum_{\sigma\in \mathcal P_n}q^{\operatorname{inv(\sigma)}}=[n]!=\sum_{\sigma\in \mathcal P_n}q^{\operatorname{inv(\sigma)}}
Proof.
\mathbf{inv} 部分\quad令 h(\sigma) 为排列 w 中在数 n 右侧的数的个数，并记 \sigma_1 为 \sigma 去掉数 n 后的结果，显然 \sigma_1\in\mathcal P_{n-1}，且有 \operatorname{inv}(\sigma)=h(\sigma)+\operatorname{inv}(\sigma_1)，故：
\begin{aligned}
\sum_{\sigma\in\mathcal P_n}q^{\operatorname{inv(\sigma)}}&=\sum_{k=0}^{n-1}\sum_{\sigma\in \mathcal P_n,h(\sigma)=k}q^{\operatorname{inv}({\sigma})}=\sum_{k=0}^{n-1}\sum_{\sigma_1\in \mathcal P_{n-1}}q^{k+\operatorname{inv}(\sigma_1)}\\
&=\sum_{k=0}^{n-1}q^{k}\sum_{\sigma_1\in \mathcal P_{n-1}}q^{\operatorname{inv(\sigma_1)}}=[n]_q\sum_{_{\sigma\in \mathcal P_{n-1}}}q^{\operatorname{inv}(\sigma)}\end{aligned}
如是递归下去。显而易见 \sum_{\sigma\in \mathcal P_1}q^{\operatorname{inv}({\sigma})}=[1]_q，立即证得 \sum_{\sigma\in \mathcal P_n}q^{\operatorname{inv(\sigma)}}=[n]_q[n-1]_q\cdots[1]_q=[n]!。
$$
\sum_{\sigma\in \mathcal P_n}q^{\operatorname{maj}(\sigma)}=\sum_{\tau\in \mathcal P_{n-1}}\sum_{k=0}^{n-1}q^{\operatorname{maj}(\tau)+k}=[n]\sum_{\tau\in \mathcal P_{n-1}}q^{\operatorname{maj}(\tau)}
$$
边界与 $\rm inv$ 的情形是类似的，可得其为 $[n]!$。$\square
一般地，如果组合统计量 f 满足：
\sum_{\sigma\in \mathcal P_{n}}q^{f(\sigma)}=[n]!
则称这样的组合统计量 f 为 \mathbf{Mahonian} 的。
定理\quad设 \mathbf{\alpha}=(m_1,m_2,\dots,m_k)\in\mathbb N^k,n=\sum_{\jmath}m_{\jmath}，令 \mathcal M_{\alpha} 表示其上所有全排列，则：
\sum_{w\in\mathcal M_{\alpha}}q^{\operatorname{inv}(w)}=\begin{bmatrix}n\\m_1\quad m_2\quad \cdots\quad m_k\end{bmatrix}_q=\sum_{w\in\mathcal M_{\alpha}}q^{\operatorname{maj}(w)}
格路径的组合统计量
Catalan 序列集与 Dyck 路集
一个序列被称之为 \mathbf n 阶 \mathbf{Catalan} 序列，如果其由 n 个 0 和 n 个 1 构成，且该序列的任一前缀中 0 的个数均不小于 1 的个数。所有 n 阶 \rm Catalan 序列构成的集合记作 \mathcal{CW}_n。
## q-Catalan 数
对于 $\mathcal D_n$ 中的一条 $\rm Dyck$ 路 $\Pi$，令 $a_i(\Pi)$ 为自下而上第 $i$ 行里 $\Pi$ 和主对角线之间的完整方格个数，并定义组合统计量 $\operatorname{area}$ ：
$$
\operatorname{area}(\Pi)=\sum_{i=1}^n a_i(\Pi)
$$
一个 $\mathbf{q-Catalan}$ **数** $C_n(q)$ 以如下形式定义：
$$
C_n(q)\sum_{\Pi\in\mathcal D_n}q^{\operatorname{area}(\Pi)}
$$
### 递推关系
**定理**$\quad$ 对任意正整数 $n$，有：
$$
C_n(q)=\sum_{k=0}^n q^{k-1}C_{k-1}(q)C_{n-k}(q)
$$
$Proof.\quad$令 $h(\Pi)$ 表示 $\Pi$ 从 $(0,0)$ 以后第一次碰到主对角线时的高度，则点 $(h(\Pi),h(\Pi))$ 将 $\Pi$ 分为 $\Pi_1,\Pi_2$ 上下两段。设 $k=h(\Pi)$，显然 $\Pi_1$ 必经过 $(0,1),(k-1,k)$ 两点。设该 $(0,1)$ 至 $(k-1,k)$ 段路径为 $\Pi_3$。于是 $1\leqslant k\leqslant n$，且 $\Pi_1\in\mathcal D_k,\Pi_2\in\mathcal D_{n-k},\Pi_3\in\mathcal D_{k-1}$，且：
$$
\operatorname{area}(\Pi)=\operatorname{area}(\Pi_1)+\operatorname{area}(\Pi_2)=k-1+\operatorname{area}(\Pi_3)+\operatorname{area}(\Pi_2)
$$
则：
$$
\begin{aligned}
C_n(q)&=\sum_{k=1}^n\sum_{\Pi\in\mathcal D_n,h(\Pi)=k}q^{\operatorname{area}(\Pi)}\\
&=\sum_{k=1}^n q^k\left(\sum_{\Pi_3\in\mathcal D_{k-1}}q^{\operatorname{area}(\Pi_3)}\times \sum_{\Pi_2\in\mathcal D_{k}}q^{\operatorname{area}(\Pi_2)}\right)\\
&=\sum_{k=0}^n q^{k-1}C_{k-1}(q)C_{n-k}(q)\end{aligned}
$$
### 另一个定理
$$
\sum_{w\in\mathcal{CW_n}}q^{\operatorname{maj}(w)}=\frac{1}{[n+1]_q}\begin{bmatrix}2n\\n\end{bmatrix}_q
$$
## 格路径与 01 序列的对应
一条从 $(0,0)$ 到 $(m,n)$ 的只由 $(0,1),(1,0)$ 步构成的路径称之为 $\mathbf{(m,n)}$ **格路径**。所有 $(m,n)$ 格路径的集合记作 $\mathcal L_{m,n}$。
记全体 $m$ 个 $1$，$n$ 个 $0$ 的 0/1 序列集合为 $\mathcal M_{m,n}$。$\mathcal L_{m,n}$ 到 $\mathcal M_{m,n}$ 有一个显然的双射：将 $0$ 与 $(0,1)$ 对应，将 $1$ 与 $(1,0)$ 对应。
设 $L\in \mathcal L_{m,n}$，令 $a_i(L)$ 为第 $i$ 行与纵坐标轴 $x=0$ 之间的方格数，定义：
$$
\operatorname{area}(L)=\sum_{i=1}^n a_i(L)
$$
**定理**$\quad$设 $L\in \mathcal L_{m,n}$ 与 $w_{L}\in \mathcal M_{m,n}$ 是上述双射对应的一对元素，则：
$$
\operatorname{area}(L)=\operatorname{inv}(w_{L})
$$
**推论**
$$
\sum_{L\in\mathcal L_{m,n}}q^{\operatorname{area}(L)}=\begin{bmatrix}m+n\\n\end{bmatrix}_q
$$
------------
# Parking 函数到树的双射
这是本文讨论的最后一个话题，也是本文介绍的主要对象之一。作为本文的最后一部分，我们将讨论经典的停车问题与标记树的联系，并给出一个双射。
## 有标号森林的基本概念
一个由有标号树构成的森林称之为**有标号森林**，特别地，有标号有根树构成的森林称为**有标号有根森林** (Rooted Labeled Forests)。记所有由 $n$ 个点构成的有标号有根森林集合为 $\mathcal F_n$。
$n$ 个点的有标号有根森林数量就是 $n+1$ 个点的标记树数量，因此有：
$$
\left|\mathcal F_n\right|=(n+1)^{n-1}
$$
这个等式可以用矩阵树定理证明，这在我们的讨论范围以外。
### 有标号有根森林的组合统计量
定义：
$$
\operatorname{inv}(F;v)=\operatorname{card}\big(\{(v,u)\mid u\in\operatorname{des}(v),u<v\}\big)
$$
其中 $\operatorname{des}(v)=\operatorname{subtree}(v)\setminus\{v\}$，即 $v$ 的子树除去 $v$ 以外的点构成的集合 (descendant)，并定义组合统计量 $\operatorname{inv}(F)$：
$$
\operatorname{inv}(F)=\sum_{v}\operatorname{inv}
(F;v)
$$
称一个节点 $v$ 是一个 **leader**，如果 $\operatorname{inv}(F;v)=0$。定义组合统计量 $\operatorname{lead}(F)$：
$$
\operatorname{lead}(F)=\operatorname{card}\big(\{v\mid v\text{ is a leader in }F\}\big)
$$
## $\mathcal{PF_n}$ 与 $\mathcal F_n$ 的几个关联
**定理**$\quad n$ 元 $\rm Parking$ 函数的数量和 $n$ 个点的有标号森林数量相等，即：
$$
|\mathcal{PF_n}|=(n+1)^{n-1}=|\mathcal F_n|
$$
这启示我们可能存在某些双射。该式的两端在上文均已解释。
### Parking 函数的组合统计量
设 $P=p_1p_2\dots p_n,P\in\mathcal{PF}_n$，$P$ 中每辆车最终停车位置为 $q_1,q_2,\dots,q_n$，令 $\operatorname{jump}(P;i)=p_i-q_i$，并令组合统计量 $\operatorname{jump}(P)$ 为：
$$
\operatorname{jump}(P)=\sum_{i=1}^n \operatorname{jump}(P;i)
$$
注意到：
$$
\begin{aligned}
\operatorname{jump}(P)&=(q_1+q_2+\dots+q_n)-(p_1+p_2+\dots+p_n)\\
&=\binom{n+1}{2}-\sum_{\jmath} p_{\jmath}
\end{aligned}
$$
对于 $P$ 的一个 $c$，称其为 **lucky** 的，如果 $ \operatorname{jump}(P;c)=0$，即，它恰好停到了偏好的位置。定义组合统计量 $ \operatorname{lucky}(P)$：
$$
\operatorname{lucky}(F)=\operatorname{card}\big(\{c\mid c\text{ is lucky}\}\big)
$$
### 组合统计量上的联系
注意到：
$$
\begin{aligned}
\sum_{F\in\mathcal{F}_1}q^{\operatorname{inv}(F)}&=1\\
\sum_{F\in\mathcal{F}_2}q^{\operatorname{inv}(F)}&=2+q\\
\sum_{F\in\mathcal{F}_3}q^{\operatorname{inv}(F)}&=6+6q+3q^2+q^3
\end{aligned}
$$
$$
\begin{aligned}
\sum_{P\in\mathcal{PF}_1}q^{\operatorname{jump}(P)}&=1\\
\sum_{P\in\mathcal{PF}_2}q^{\operatorname{jump}(P)}&=2+q\\
\sum_{P\in\mathcal{PF}_3}q^{\operatorname{jump}(P)}&=6+6q+3q^2+q^3
\end{aligned}
$$
事实上，这的确是一个一般的规律。我们有：
1. **定理** (G.Kreweras 1980)
$$
\sum_{F\in\mathcal{F}_n}q^{\operatorname{inv}(F)}=\sum_{P\in\mathcal{PF}_n}q^{\binom{n+1}{2}-|P|}
$$
2. **定理** (Gessel-Seo 2004)
$$
\sum_{F\in\mathcal F_n}u^{\operatorname{lead}(F)}=u\prod_{i=1}^{n-1}(i+(n-i+1)u)=\sum_{P\in\mathcal{PF}_n}u^{\operatorname{lucky}(P)}
$$
3. **定理** (S. 2008)
$$
\sum_{F\in\mathcal F_n}q^{\operatorname{inv}(F)}u^{\operatorname{lead}(F)}=\sum_{P\in\mathcal{PF}_n}q^{\operatorname{jump}(P)}u^{\operatorname{lucky}(P)}
$$
至此，我们可以进入本文最终的部分。
## 停车问题与树的双射
### 映射 $\varphi:\mathcal {F_n}\to\mathcal{PF}_n
考虑任意一个 n 有标号有根森林 F。新增一个节点 n+1，并将所有根向节点 n+1 连边，形成一棵以 n+1 为根的标记树，记作树 T。借用一张里昂大学的一篇课件上的图：
现在，我们对这棵树的每一个节点 x 的子树进行如下操作：
- 取出 x 后代中标号大于 x 的节点；
- 保序地重排这些节点，即将取出的节点从小到大排名为 a_1,a_2,\dots,a_m，令 a_i(i<m) 移动到原先 a_{i+1} 的位置；
- 将 x 移动到 a_1 的位置，将 a_m 移动到 x 的位置。
易见点的操作顺序不影响结果，且操作后形成的树唯一。对每一个 x 都如是操作后，我们将得到一棵对于任意节点（不妨设其标号为 x）都有 x 大于其任意后代标号的树。我们将这棵新树记作 D。
但是有多棵树都有可能重排出树 D。为此，我们引入：
- 树 I：与树 T 结构相同，其每个点的点权为树 T 中该点的 \mathrm{inv}。
- 树 C：与树 T 结构相同，其每个点的点权为对其后根遍历所得的次序。
将树 D,C,I 结合，构成树 D\times(C-I)，即：每个点有一个标号 x 和一个点权 v(x)，其中 x 即为树 D 中的 x，v(x) 为树 C 中该点的点权减去树 I 中该点的点权。
由此，我们可以还原出树 T。并且，我们已经得到了 \mathcal F_n\to\mathcal{PF}_n 的一个单射：按标号依序取出每个点 x，则 v(x) 即为车 x 的偏好停车位置。例如在上图中，这个 \rm Parking 函数 P 为：
逆映射：\varphi^{-1}:\mathcal{PF}_n\to\mathcal{F}_n
考虑任意一个 \rm Parking 函数 P。这里以上文出现过的例子为例：
P=\text{
10\;
2\;
6\;
5\;
7\;
1\;
13\;
10\;
4\;
1\;
14\;
9\;
11
}
该 \rm Parking 函数给出了一个最终的停车序列。在上例中：
\begin{aligned}
\mathrm{Parking\;Space}&=1\;\;2\;\;3\;\;\;\,4\;\;5\;\;6\;\;7\;\;\,8\;\;\;\,9\;\;\;\,10\;\;11\;\;12\;\;13\;\ 14\quad\,\,\,15\\
\mathrm{Car's\;Number\;}c&=6\;\;2\;\;10\;\;9\;\;4\;\;3\;\;5\;\;14\;\;12\;\;1\;\;\;\,8\;\;\;\;13\;\;\,7\;\;\ \,11\quad\ \,15\\
\mathrm{jump}(P;c)&=0\;\;0\;\;2\;\;\;\,0\;\;0\;\;0\;\;0\;\;3\;\;\;\;0\;\;\;\,0\;\;\;\;1\;\;\;\,1\;\;\;\;\,0\;\;\;\,0\quad\ \ \,\,14
\end{aligned}
现在，对于每一个停车位 x，设其上停的车为 c(x)，则将 x 向其后第一个 c(y)>c(x) 的停车位 y 连边。
我们就获得了树 T,C 和 I。易见其是唯一的，且任意一个 \rm Parking 函数 P\in\mathcal{PF}_n 都能如是构建出相应的树。这样，我们就完成了 \varphi^{-1}:\mathcal{PF}_n\to\mathcal F_n。
至此，我们解释了 \mathcal{PF}_n 与 \mathcal F_n 的集合大小相等的原因，并对其组合统计量间的联系给出了一个直观的表示。
参考文献：
- 组合数学 / 冯荣权，宋春伟编著。北京大学出版社，2015.8
- Forests and Parking Functions , Heesung Shin, Institut Camille Jordan, Université Claude Bernard Lyon-I, France. (THE 61ST SÉMINAIRE LOTHARINGIEN DE COMBINATOIRE. CURIA, PORTUGAL, SEP. 24, 2008)
- U 群神仙的答疑