升降阶乘与 Stirling 换基

$x^n$ 把每个位置都看成有 $x$ 个选择，允许重复。$x^{\underset{―}{n}}$ 则依次排除已经用过的选择，天然适合不重复选择。两种表达保存的是同一个多项式，选择合适坐标可以把问题中的结构显露出来。

为什么这些确实是基？第 $n$ 个阶乘多项式是首一的 $n$ 次多项式。任意非零多项式，先减掉最高项系数乘相应阶乘多项式，次数就下降；反复进行一定终止，证明能展开。若两份展开不同，取不同系数的最高下标，其首项无法由较低次数抵消，证明展开唯一。

从函数的纤维证明第二类换基 ​

先让 $x=m$ 为任意非负整数。$m^n$ 数函数 $f:[n]\to [m]$。按非空纤维数 $k$ 分类，先把 $[n]$ 划成 $k$ 个无标签非空块，有 $S(n,k)$ 种；再给这 $k$ 个不同的块指派互异像，恰有 $m^{\underset{―}{k}}$ 种。每个函数的纤维唯一，所以两边相等。双方都是 $x$ 的多项式，并在无限多个整数上一致，故恒等。

第一类数页的循环插入已证明上升阶乘式。把 $x$ 换为 $-x$，再乘 $(-1{)}^n$，就得到下降阶乘的有符号展开。同样替换第二类式得到上升版。于是符号不是新计数约定，而是变量反号带来的换基系数。

把 $x^n$ 展开成下降阶乘，再逐个展开成普通幂，比较 $x^j$ 系数，得到

反向展开也给 $\sum _{k=j}^{n}s(n,k)S(k,j)={\delta }_{nj}$。两式明确了哪个下标是行、哪个是列，随后对任意序列线性组合便得到反演。

四次的两向公式是

在 $x=3$ 处，第一式右侧为 $0+6\cdot 6+7\cdot 6+3=81$。这里 $S(4,2)=7$ 与 $c(4,2)=11$ 扮演两个不同方向的角色，不能互换。

检查反演矩阵的 $(4,2)$ 元素：

若误用无符号 $c$，将得到 $7+18+11=36$，恰暴露“去掉负号仍互逆”的错误。

下降阶乘是多项式，在任意 $x$ 都能代入。但 $m^{\underset{―}{k}}$ 作为单射计数的解释要求 $m$ 为非负整数；负数或非整数代入只表示代数值。另一个边界是二项式基 $(\genfrac{}{}{0ex}{}{x}{k})=x^{\underset{―}{k}}/k!$：在特征 $p$ 时，$k\ge p$ 的除法可能无定义。本页选择特征零，后续有限差分也遵守同一约定。

把 $x^{\underset{―}{k}}$ 除以 $k!$ 后，前向差分理路有限差分的离散微积分Calculus of finite differences · Newton forward expansion · 前向差分算子用前向差分恢复多项式、判定整数格上的次数，并通过二项式基求离散原函数和幂和。恰把 $(\genfrac{}{}{0ex}{}{x}{k})$ 降为 $(\genfrac{}{}{0ex}{}{x}{k-1})$。因此有限差分表给出的不是神秘的新坐标，而是同一个多项式在二项式基中的系数。

Ferrers 棋盘理路Ferrers 棋盘的阶乘因式分解Ferrers rook factorization · Factorial rook polynomial · Goldman–Joichi–White factorization以嵌套行的双计数证明阶乘车多项式线性分解，算出阶梯板车数并构造集合划分的弧编码。把车数放到下降阶乘基里，获得一个线性因子的乘积。Lah 数理路Lah 数与线性有序块Unsigned Lah numbers · List partition numbers区分块内线性顺序与块间无序，证明Lah闭式和插入递推，再连接升降阶乘和两类Stirling数。进一步直接连接上升与下降两组基，说明块内“无序、循环序、线性序”三种结构怎样对应三种系数三角形。

若把序列反演翻译到 EGF，$b_n=\sum _{k}S(n,k)a_k$ 等价于 $B(z)=A(e^z-1)$；固定 $k$ 的第二类 EGF 是 $(e^z-1{)}^k/k!$，逐系数求和即可证明。其逆为 $A(z)=B(\log (1+z))$，因为两个内层级数常数项为零且互为复合逆。这一代换是旧 EGF 工具的具体应用，不需要新建一份“Stirling 生成函数”正本。