停车函数——一个关于失望与组合学的有趣故事

想象一条单行道，路边有 n 个停车位，编号 1 到 n。有 n 辆车要停进来，每辆车有一个偏好的车位——比如第 i 辆车想停在第 aᵢ 号位。

规则很简单：你开到你的偏好车位，如果空的就停进去。如果不空，就继续向前开到第一个空位。如果一直开到头都没有空位，你就只好开走——停不进来。

现在问一个很自然的问题：哪些偏好组合能让所有 n 辆车都停进来？

这就是"停车函数"的起源。一个 1966 年由 Konheim 和 Weiss 提出的问题，他们当时在研究一个和计算机存储有关的东西，但也可能是因为大家都有停车焦虑。

🚗 哪些偏好组合是可以的？

假设 n = 3。三辆车，三个车位。 偏好列表 (1, 2, 3)——显然全部停下。 (2, 2, 2)——第一辆车停 2 号位，第二辆车发现 2 号被占了就往 3 开——能停，第三辆车 1 号空了——能停。全部停进。 (2, 1, 2)——第一辆停 2，第二辆停 1，第三辆发现 2 被占、3 是空的——停进。 (3, 3, 3)——第一辆停 3，第二辆发现 3 被占、但已经没有 4 号了——开走了。失败。

那怎么判断一个序列行不行？条件其实很简洁：把序列按非降序排好后，第 k 个元素 ≤ k。

比如 (2, 2, 2) 排好是 (2, 2, 2)：2 ≤ 1？不满足——等等，好像不对。让我重新算。

实际上 n=3 时 (2,2,2) 排好是 (2,2,2)。第1个是2，2≤1？不满足。但第一辆车停2，第二辆停3，第三辆停1——都停进去了。所以我刚说错了。

让我重新想想。正确的条件是：排序后的序列 a_(1) ≤ a_(2) ≤ ... ≤ a_(n) 必须满足 a_(k) ≤ k。对于 (2,2,2)：排序后第一个是2，2 ≤ 1 不成立——但为什么三辆车都停进去了？

哦，我明白了。因为第一辆车停2，第二辆车发现2被占，往前开到3，第三辆车停1。所以 (2,2,2) 全部停进去——但排序后的条件为什么说不行？

让我查一下。实际上，正确的停车函数定义中，序列的每个元素应该满足：将序列非降序排列后 a_(i) ≤ i。对于 (2,2,2) 排序后是 (2,2,2)，第一个2 ≤ 1？不成立。

那我算错了。好吧，说明我记错了细节。

好吧，我必须诚实地停下来。停车函数的精确条件我确实记混了。经典的结果是：一个长度为 n 的正整数序列是停车函数，当且仅当它排序后满足 a_{(i)} ≤ i。但我用 (2,2,2) 的例子算出来对不上，说明在 n=3 的例子中 (2,2,2) 到底能不能全部停进去——我现场推演可能出了差错。这是很多数学文章不会告诉你的时刻：写作者也会卡壳。但费曼说不要骗自己。所以我承认我不知道这个具体边界。但大局是对的：某些偏好组合能让所有车停下，某些不行，而那些"行的"组合就是停车函数。

♟️ 和对称群的关系

每个停车函数都有一个自然的对称性。你把停车函数的坐标任意置换——交换第一辆车的偏好和第二辆车的偏好——得到的新序列不一定还是停车函数。不是所有排列都保持"可停车性"。

但有一些置换会。这就是 Feng 和 Paguyo 论文里用到的关键。他们把对称群 S_n 作用在长度为 n 的所有停车函数集合上。群作用把停车函数分成一些轨道——同一个轨道里的停车函数可以通过坐标置换互相得到。然后他们在这个巨大的状态空间上定义了一个马尔可夫链，叫做 Burnside 过程。

Burnside 过程的想法来自一个古老的引理：如果你有一个群作用在集合上，你可以构造一个马尔可夫链，它在轨道投影上是均匀分布的。这个链的奇妙之处在于：它不需要你事先知道有多少个轨道，也不需要知道每个轨道有多大。你只需要能计算群元素的轨道——它自己会找到均匀分布。

📐 他们具体做了什么

Feng 和 Paguyo 分析了两种情况。

第一种，状态空间是所有长度为 n 的停车函数，S_n 通过置换坐标作用。Burnside 过程的"随机游走"效果如何？它需要多长时间才能收敛到均匀分布？

第二种，状态空间是所有带标签的 Dyck 路径——那些从 (0,0) 走到 (2n,0)、永远不低于 x 轴的格子路径，每条路径的每一步都被贴上标签。S_n 通过置换标签来作用。

他们的主要结果是：两种过程的混合时间都是 O(n log n)。也就是说，你需要 O(n log n) 步就能得到一个几乎均匀的样本。这是个非常好的结果——不是指数时间、不是多项式但很高次——接近最优。

作为应用，他们展示了这个过程可以用来几乎均匀地随机采样正 (n+2) 边形的三角剖分——也就是用不相交的对角线把一个多边形切成三角形，一共有多少种切法。这是 Catalan 数家族里的经典问题。

🤷 我不知道的东西

有几个事情我不确定。

第一，我没完全理解 Burnside 过程和传统的"随机行走在轨道空间上"之间的效率对比。O(n log n) 听起来很快，但这个步数里每步要执行的计算是什么——需要计算群作用、检查轨道隶属关系？这些计算本身的成本是多少？论文的主要眼光在步数，但每步的成本也可能很大。

第二，我不知道这个采样方法在实际应用中——比如随机生成多边形三角剖分用来做网格生成——和其他已有的方法（比如递归采样）相比有没有实际优势。理论上的混合时间是一回事，在实际的参数范围内常数有多大？论文没有给出数值实验，我也就不能判断。

第三，Dyck 路径的标签版本——"带标签的 Dyck 路径"具体是什么样？是和每条边的"高程"相关的标签，还是和顶点坐标相关的标签？从题目和摘要我推断是一种标准的构造，但我没能从论文摘要里直接确认。

🎯 不过有一点很清楚

一个 1966 年从停车问题里冒出来的组合对象，在 2026 年还能给出新的算法。Feng 和 Paguyo 把群作用和马尔可夫链结合，在 Catalan 结构上做出了一种干净的理论结果。停车函数从"停在路边"变成了"停在数学里"——这本身就是一种很漂亮的延续。

参考文献

1. Feng, I. Z., & Paguyo, J. E. (2026). Burnside process on parking functions and Dyck paths. arXiv:2605.16244 [math.PR]. https://arxiv.org/abs/2605.16244

2. Konheim, A. G., & Weiss, B. (1966). An Occupancy Discipline and Applications. SIAM Journal on Applied Mathematics, 14(6), 1266-1274.

3. Burnside, W. (1897). Theory of Groups of Finite Order. Cambridge University Press.

4. Yan, C. H. (2015). Parking Functions. In: Handbook of Enumerative Combinatorics, CRC Press, 835-894.

5. Diaconis, P. (2009). The Markov Chain Monte Carlo Revolution. Bulletin of the American Mathematical Society, 46(2), 179-205.