第一类 Stirling 数

增加最大标签 $n$ 时，只有两种互斥选择。它可以自己成为一个循环 $(n)$，于是旧排列少一个循环；也可以插入旧循环的一条箭头中，循环总数保持不变。

第二种情况恰有 $n-1$ 个插入位置。对于每个旧元素 $a$，原来的箭头 $a\mapsto b$ 改成 $a\mapsto n\mapsto b$；插入位置由 $a$ 唯一指定。反向删掉 $n$ 并把其前驱直接接到后继，就恢复旧排列和那个位置。循环记号的旋转书写不会额外创造位置。

例如从 $(13)(2)$ 出发，把 $4$ 插到 $1$ 后得到 $(143)(2)$；插到 $3$ 后得到 $(134)(2)$；插到 $2$ 后得到 $(13)(24)$。三份结果与三个旧元素一一对应。

把递推乘 $u^k$ 并求和，得到 $C_n(u)=(u+n-1)C_{n-1}(u)$。从空排列开始连乘便证明阶乘积，而不是从一个已知积式倒猜计数含义。

从空行起算，$n=0,1,2,3,4$ 的非零部分依次为

其中 $c(4,2)=c(3,1)+3c(3,2)=2+9=11$。不依赖递推的核验按循环型分类：一个三循环加一个固定点有 $(\genfrac{}{}{0ex}{}{4}{3})\cdot 2=8$ 份；两个二循环有 $3$ 份，合计十一。一个四循环有 $3!=6$ 份；一个二循环加两固定点有 $(\genfrac{}{}{0ex}{}{4}{2})=6$ 份；四固定点有一份，总计二十四。

因此

前式 $u=1$ 得 $4!$；后式 $u=1$ 得零，后者不是排列总数。这里的负号服务于基变换，而非“负数个排列”。

循环有方向：$(123)$ 与 $(132)$ 不同；只是循环起点可以旋转。集合划分的三元块只有一个无序集合，所以第二类 Stirling 数理路第二类 Stirling 数Stirling number of the second kind把 n 元集合划分为 k 个非空无标号块的方案数。不会给它两种方向。两类数在 $n=3,k=2$ 碰巧相等，不能据一个小值认作同一统计。

循环构造理路组合类的循环构造Cycle construction in combinatorics · CYC construction将非空组件序列按循环旋转取商，并用对数或 Euler φ 修正翻译其旋转对称性的构造。已经给出排列是循环的无序集合。本页补足的插入证明与该规格独立相容：每个非空标号循环的EGF理路指数生成函数Exponential generating function · EGF以 a_n x^n/n! 编码带标号组合对象计数序列的形式幂级数。为 $\sum _{m\ge 1}{z}^m/m=\log (1/(1-z))$，用 $u$ 标记循环数，得

在 $\mathbb{Q}[u][[z]]$ 中每个系数都是有限多项式；记成 $(1-z{)}^{-u}$ 是这项形式定义，不需要先把 $u,z$ 当数值。固定 $k$ 取系数得到 $\sum _{n}c(n,k)z^n/n!={\log }^k(1/(1-z))/k!$。

阶乘基变换理路升降阶乘与 Stirling 换基Falling factorial basis · Rising factorial · Stirling inversion在特征零多项式中建立普通幂、下降阶乘、上升阶乘三组坐标，以计数和三角性证明两类Stirling互逆。把有符号版本与第二类数配成互逆矩阵。Foata 基本变换理路Foata 基本变换Foata fundamental transformation · Fundamental bijection on permutations通过标准循环书写与纪录位置切分构造互逆双射，证明循环数对应纪录数、下降数对应亏位并迁移到超越统计。则给另一种完整统计：有 $k$ 个循环的排列，与单行列表有 $k$ 个从左到右新纪录的排列一样多。一个结论通向代数换基，另一个通向结构双射，不能用“都是同一张数表”替代证明。