Eulerian 数与排列下降

与数循环不同，这次在列表的缝里插入最大元素 $n$。旧列表长度为 $n-1$，共有 $n$ 条缝，包括两端。若旧下降数为 $k$，插入已有下降缝 $a>b$ 时，$a>b$ 被 $a<n>b$ 代替，下降数不变；插在末尾也不变。因此保持 $k$ 的位置有 $k+1$ 个。

若旧下降数为 $k-1$，要把它增加到 $k$，可插在旧上升缝，或插到最前。旧列表有 $n-2-(k-1)=n-k-1$ 条上升缝，加上前端，共 $n-k$ 个位置。删去唯一最大元能恢复原列表和插入位置，所以没有重复。

例如旧列表 $213$ 有一个下降。插入 $4$ 到 $2|1$ 或末尾得 $2413,2134$，仍为一个下降；插在最前或 $1|3$ 得 $4213,2143$，都变成两个下降。这比“插入后通常多一个”更准确。

递推得到

其中 $A(4,1)=2\cdot 4+3\cdot 1=11$。独立按唯一下降的位置列全十一份：

• 下降在位置一：$2134,3124,4123$
• 下降在位置二：$1324,1423,2314,2413,3412$
• 下降在位置三：$1243,1342,2341$

升序列表只有一个，降序列表也只有一个。把每项 $a$ 替为 $n+1-a$，原下降恰变上升，因此 $A(n,k)=A(n,n-1-k)$；这将十一份一降排列一一对应到十一份二降排列。总和 $1+11+11+1=24$ 再核对全排列数。

下降只比较相邻位置。$312$ 有一个下降，却有两个逆序对 $(3,1),(3,2)$。逆序数的生成多项式是 $1+2q+2q^2+q^3$（$n=3$），与 $A_3(q)$ 不同。另一个叫 Euler 数的序列计交替排列，也不等于本页的 Eulerian 数。

若符号允许重复，例如 $112$，插入和对称性都要重新分析。互异标签保证每对相邻值恰好“上升或下降”，没有相等分支；不能无说明沿用 $n!$ 总数或 $n-1-k$ 对称式。

把排列拆成极大的连续递增段，段数恰为下降数加一。例如 $2413$ 拆成 $24|13$。这解释有些教材用递增段数编号，并把 Eulerian 多项式定义成 $t{A}_n(t)$。Stanley 本页所链书稿在 $n\ge 1$ 时采用这一偏移约定，DLMF 与本页采用零下降约定。

Worpitzky 恒等式理路Worpitzky 恒等式与幂的下降展开Worpitzky identity · Eulerian power identity用稳定排序把任意函数唯一分到下降模式，证明Worpitzky展开并推导幂和有理生成函数、Eulerian显式式与EGF。通过稳定排序把任意函数按下降分组，推导

进一步得到EGF理路指数生成函数Exponential generating function · EGF以 a_n x^n/n! 编码带标号组合对象计数序列的形式幂级数。 $\sum _{n\ge 0}{A}_n(t)z^n/n!=(1-t)/(e^{(t-1)z}-t)$；完整推导及 $t=1$ 的可去形式在该页处理，不能把 $0/0$ 当数值代入。

若需指定下降的确切位置，应使用下降集合计数理路排列下降集合的精确计数Descent-set enumeration · Exact descent set · MacMahon descent-set formula先数下降只能出现在指定切口的排列，再用子集容斥恢复恰好下降集合，区分位置统计与下降总数。。若统计的是 $\pi (i)>i$ 的超越位置，则需Foata 双射理路Foata 基本变换Foata fundamental transformation · Fundamental bijection on permutations通过标准循环书写与纪录位置切分构造互逆双射，证明循环数对应纪录数、下降数对应亏位并迁移到超越统计。才知道它和下降数等分布；同一份排列的两个数不必相等。

若除了下降数，还要保留下降发生位置的总和，应使用Carlitz 联合多项式理路Carlitz q-Eulerian 联合多项式Carlitz q-Eulerian polynomial · Euler–Mahonian distribution · Descent major-index polynomial按插入缝的主指标增量推导下降与主指标联合递推，并由稳定排序与差分参数给出加权Worpitzky生成函数。 $A_n(t,q)=\sum _w{t}^{\mathrm{des}(w)}{q}^{\mathrm{maj}(w)}$。最大元插入的每条缝有不同主指标增量，因而本页的整数缝数细化为 $q$ 整数权重；例如四阶的一次下降给 $3q+5q^2+3q^3$，而在 $q=1$ 才汇总成十一。