Worpitzky 恒等式与幂的下降展开

先取正整数 $x=m$。左边数所有函数 $f:[n]\to [m]$。将标签 $i$ 按 $(f(i),i)$ 的字典序排列：先按函数值从小到大；值相同时按标签从小到大。这就是固定了打平规则的稳定排序，得到唯一排列 $\pi$。

沿这份排列，值 $a_i=f({\pi }_i)$ 满足

若标签出现下降，却让两个函数值相等，就违反了相等时标签递增的规则。反过来，任何满足这些条件的值序列都唯一恢复一个稳定排序为 $\pi$ 的函数。

设 $\pi$ 有 $k$ 个下降，令 $d_i$ 为位置 $i$ 之前的下降数，取 $b_i=a_i-d_i$。则严格增加处的强制一步被消去，得到

隔板法理路隔板法Stars and bars把相同对象分入有标号盒子的整数解计数方法。给这样的弱递增序列数为 $(\genfrac{}{}{0ex}{}{m-k+n-1}{n})$；当 $m\le k$ 时没有解，且此处上参数在 $0,\dots ,n-1$，组合数也为零。按 $k$ 汇总全部稳定排序就得第一式。再由双方多项式在无限多个正整数上一致，得到任意 $x$ 的恒等式。

$n=3,m=2$ 时，

没有下降的 $123$ 对应四份弱递增二值序列 $111,112,122,222$。一个下降的四份排列各有唯一适合的二值序列。例如 $\pi =213$ 要求 $a_1<a_2\le a_3$，只能是 $(1,2,2)$，恢复函数值 $(f(1),f(2),f(3))=(2,1,2)$。两次下降的 $321$ 需要三个不同值，二值集合无法提供。

$n=4,m=2$ 时，$16=(\genfrac{}{}{0ex}{}{5}{4})+11(\genfrac{}{}{0ex}{}{4}{4})=5+11$。这从函数的另一种分类独立核验 $A(4,1)=11$。

必须固定相等值的打平规则。如果同一函数值相等时任意排列标签，一份函数会落入多份 $\pi$，导致重复计数。例如常值函数本应只落到 $123\cdots n$，不能对它贡献 $n!$ 份。这里的函数值也有自然顺序；只给一个无序颜色集，须先选定颜色顺序再使用这份分解。

令 $A_n(t)=\sum _{k}A(n,k)t^k$。对 $n\ge 1$ 将上式取整数 $m\ge 0$，再作普通生成函数理路普通生成函数Ordinary generating function把序列编码为形式幂级数 Σ a_n x^n。。由移位二项式级数，

例如 $n=3$ 为 $t(1+4t+t^2)/(1-t{)}^4$。乘回 $(1-t{)}^{n+1}$ 并取 $t^{k+1}$ 系数，得到

$n=4,k=1$ 时为 $2^4-5\cdot 1^4+10\cdot 0^4=11$。

还可以完整推导Eulerian 的 EGF理路指数生成函数Exponential generating function · EGF以 a_n x^n/n! 编码带标号组合对象计数序列的形式幂级数。。令 $E(z,t)=\sum _{n\ge 0}{A}_n(t)z^n/n!$。把上面的幂级数关系乘 $z^n/n!$ 并对 $n\ge 1$ 求和，得

整理、再令 $z=(1-t)w$，得到

上面的双和先在 $\mathbb{Q}[[t,z]]$ 中逐系数成立：固定 $t^m{z}^n$ 时只对应一个 $m$ 和一个指数项。每个 $z^n$ 系数再由前述幂和公式识别为 $t$ 的有理函数，因而可转入 $\mathbb{Q}(t)[[z]]$ 作整理与缩放；最终 $E$ 的每个 $w^n$ 系数仍是多项式。$t=1$ 处应按系数代入 $A_n(1)=n!$，得到 $E(w,1)=1/(1-w)$；不能把右边未经消去的 $0/0$ 当数值答案。若要在复数点求值，还需另行检查解析收敛。