Lah 数与线性有序块

无序块 $\{1,2,3\}$、循环 $(123)$、列表 $123$ 不是同一结构。三元素的一个无序块只有一份；循环有两份，因为可旋转起点；列表有六份，因为首位与方向都重要。第二类 Stirling、第一类 Stirling与 Lah 数分别数这三种块结构。

证明闭式时，先把 $n$ 个元素排成一条长列表，再从 $n-1$ 个内部缝隙选 $k-1$ 处切开。得到有先后顺序的 $k$ 个非空列表，共 $n!(\genfrac{}{}{0ex}{}{n-1}{k-1})$ 份。忘掉列表间顺序时，每个最终对象恰有 $k!$ 份原像：各块含不同标签，不会因为两块长度相同而合并。除以 $k!$ 得闭式。

插入最大元 $n$ 时，它若单独成块，贡献 $L(n-1,k-1)$。否则向已有 $k$ 个列表内部或两端插入：长度为 $\ell$ 的列表有 $\ell +1$ 个位置，全部列表总长为 $n-1$，所以一共 $(n-1)+k$ 个位置。删去 $n$ 可逆地恢复插入记录，证明递推。

$n=3,k=2$ 时，一个二元素列表与一个单元素列表：选单元素有三种，另一块有两种顺序，共六份。例如 $\{12,3\}$ 与 $\{21,3\}$ 不同，但 $\{12,3\}$ 与 $\{3,12\}$ 相同。

第四行是

用递推算 $L(4,2)=L(3,1)+5L(3,2)=6+30=36$；独立闭式给 $4!(\genfrac{}{}{0ex}{}{3}{1})/2!=36$。对比相同位置的 $S(4,2)=7$ 与 $c(4,2)=11$，块内结构增加使数目增加，却没有简单的统一倍数：不同块大小提供不同的内部顺序数。

允许空列表会破坏上述证明。固定 $k$ 时，不同空块的交换不产生新记录，忘掉块间顺序的原像数不再统一为 $k!$；若还不固定块数，就可以任意添加空块，固定总大小也会有无限多种块数。若块间也有顺序，数量应乘 $k!$；若块内改成循环顺序，应使用第一类 Stirling 数。这三个限定分别控制不同的对称性，不能用“分组后排列”一句话含糊带过。

在升降阶乘理路升降阶乘与 Stirling 换基Falling factorial basis · Rising factorial · Stirling inversion在特征零多项式中建立普通幂、下降阶乘、上升阶乘三组坐标，以计数和三角性证明两类Stirling互逆。之间，Lah 数给直接换基：

一个完整的代数证明是归纳。若第 $n$ 行成立，将两边乘 $x+n$，并使用

比较系数正得到 $L(n+1,k)=L(n,k-1)+(n+k)L(n,k)$，与插入递推和初值相同。第二式把第一式的 $x$ 换为 $-x$ 后整理即得。

$n=3$ 时为 $x(x+1)(x+2)=6x+6x(x-1)+x(x-1)(x-2)$。在 $x=2$ 处核验 $24=12+12+0$。再把上升阶乘先换成普通幂，再换成下降阶乘，唯一性给

$n=4,k=2$ 时为 $11\cdot 1+6\cdot 3+1\cdot 7=36$。这解释为什么前页把无符号第一类误当逆矩阵时得到36：它算出了第三种真实结构，而不是零。

一个非空标号列表在大小 $m$ 时有 $m!$ 份，故EGF理路指数生成函数Exponential generating function · EGF以 a_n x^n/n! 编码带标号组合对象计数序列的形式幂级数。为 $z/(1-z)$。$k$ 个互不共享标签的无序非空列表给

取 $z^n$ 系数恢复闭式。这是现有 EGF 标签分配规则的检验，不需要为列表集合新造另一套符号法。