前言

目录

• 格路径的基本概念
  • 卡特兰数与 $\rm Dyck$ 路
    • 左右子树地位不等同的二叉树计数
  • $\rm Schröder$ 数
• $\rm Parking$ 函数的基本概念
  • 判定
  • $\rm Parking$ 函数到 $\rm Dyck$ 路的映射
  • $\rm Parking$ 函数的计数
• $q\text -$模拟与组合统计量
  • $q\text -$模拟
  • 排列上的组合统计量
• 格路径的组合统计量
  • $\rm{q{-}Catalan}$ 数
  • 格路径与 $01$ 序列的对应
• $\rm Parking$ 函数到树的双射
  • 有标号森林的基本概念
  • $\mathcal{PF}_n$ 与 $\mathcal F_n$ 的几个关联
  • 停车问题与树的双射
    • 映射 $\varphi:\mathcal {F_n}\to\mathcal{PF}_n$
    • 逆映射：$\varphi^{-1}:\mathcal{PF}_n\to\mathcal{F}_n$

---

格路径的基本概念

卡特兰数与 Dyck 路

$$\binom{p+q}{q}-\binom{p+1+q-1}{q-1}=\frac{p-q+1}{p+1}\binom{p+q}{q}$$ $$C_n=\frac{1}{n+1}\binom{2n}{n}$$

Delannoy 数

$$D(p,q:r)=\binom{p+q-r}{p-r\quad q-r\quad r}$$ $$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=\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}$$ $$\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=\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+\circ+\mathcal B{\times}{\circ}+{\circ}{\times}\mathcal B+\mathcal B{\times}{\circ}{\times}\mathcal B$$

Schröder 数

$$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!}$$ $$R_n=\sum_{k=0}^n\frac{1}{n-k+1}\frac{(2n-k)!}{k!((n-k)!)^2}$$

生成函数

$$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}$$ $$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)=1+zR(z)+zR^2(z)$$ $$R(z)=\frac{1-z-\sqrt{z^2-6z+1}}{2z}$$

Parking 函数的基本概念

停车问题

判定

• 充分性：假设满足该判定且位置 $n+1$ 有车，则必有一个 $i\leqslant n$ 无车。则此时偏好 $1\sim i$ 的车仅有 $i-1$ 辆，矛盾。
• 必要性：位置 $n+1$ 无车，表明对于任意 $i\leqslant n$，位置 $1$ 至 $i$ 均停满车，即 $b_i\leqslant i$。

Parking 函数到 Dyck 路的映射

Parking 函数的计数

$$(n+1)^{n-1}$$

---

$q\text -$模拟与组合统计量

$q\text -$模拟

$$[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]!}$$ $$\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]!}$$

$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 性质）

$$\operatorname{inv(w)}=\sum_{i<j,w_i>w_j}1\,,\quad\operatorname{maj(w)}=\sum_{w_i>w_{i+1}}i$$ $$\sum_{\sigma\in \mathcal P_n}q^{\operatorname{inv(\sigma)}}=[n]!=\sum_{\sigma\in \mathcal P_n}q^{\operatorname{inv(\sigma)}}$$ $$\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_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)}$$ $$\sum_{\sigma\in \mathcal P_{n}}q^{f(\sigma)}=[n]!$$ $$\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 路集

q-Catalan 数

$$\operatorname{area}(\Pi)=\sum_{i=1}^n a_i(\Pi)$$ $$C_n(q)\sum_{\Pi\in\mathcal D_n}q^{\operatorname{area}(\Pi)}$$

递推关系

$$C_n(q)=\sum_{k=0}^n q^{k-1}C_{k-1}(q)C_{n-k}(q)$$ $$\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 序列的对应

$$\operatorname{area}(L)=\sum_{i=1}^n a_i(L)$$ $$\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 函数到树的双射

有标号森林的基本概念

$$\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{inv}(F)=\sum_{v}\operatorname{inv} (F;v)$$ $$\operatorname{lead}(F)=\operatorname{card}\big(\{v\mid v\text{ is a leader in }F\}\big)$$

$\mathcal{PF_n}$ 与 $\mathcal F_n$ 的几个关联

$$|\mathcal{PF_n}|=(n+1)^{n-1}=|\mathcal F_n|$$

Parking 函数的组合统计量

$$\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}$$ $$\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$

• 取出 $x$ 后代中标号大于 $x$ 的节点；
• 保序地重排这些节点，即将取出的节点从小到大排名为 $a_1,a_2,\dots,a_m$，令 $a_i(i<m)$ 移动到原先 $a_{i+1}$ 的位置；
• 将 $x$ 移动到 $a_1$ 的位置，将 $a_m$ 移动到 $x$ 的位置。

• 树 $I$：与树 $T$ 结构相同，其每个点的点权为树 $T$ 中该点的 $\mathrm{inv}$。
• 树 $C$：与树 $T$ 结构相同，其每个点的点权为对其后根遍历所得的次序。

逆映射：$\varphi^{-1}:\mathcal{PF}_n\to\mathcal{F}_n$

$$P=\text{ 10\; 2\; 6\; 5\; 7\; 1\; 13\; 10\; 4\; 1\; 14\; 9\; 11 }$$ $$\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}$$

---

1. 组合数学 / 冯荣权，宋春伟编著。北京大学出版社，2015.8
2. 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)
3. U 群神仙的答疑