排列下降集合的精确计数

形式陈述

对 $n\ge1$ 、 $S\subseteq[n-1]$ ，记

\alpha_n(S)=|\{\pi\in S_n:\operatorname{Des}(\pi)\subseteq S\}|, \quad \beta_n(S)=|\{\pi\in S_n:\operatorname{Des}(\pi)=S\}|.

下降集合使用严格比较 $\pi_i>\pi_{i+1}$ 。设 $S=\{s_1<\cdots<s_r\}$ ，补 $s_0=0,s_{r+1}=n$ ，并令 $a_i=s_i-s_{i-1}$ 。则

\alpha_n(S)=\frac{n!}{a_1!\cdots a_{r+1}!}, \qquad \beta_n(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}\alpha_n(T).

其中 $\alpha_n(\varnothing)=\beta_n(\varnothing)=1$ 。空排列另取 $n=0$ 时只有空下降集合，数量也为一，不将 $[n-1]$ 当作负长度的标签集。

直觉

指定 $S$ 先只表示“允许下降的切口”。在其他相邻位置，排列必须递增，所以切口之间的每段一旦知道使用哪些标签，内部次序就唯一了。先为每段分配互不共享的标签集，所需的多项式系数正是 $n!/(a_1!\cdots a_{r+1}!)$ 。

但在允许的切口处，两个相邻段接起来仍可能上升。因此直接乘多项式系数数的是“下降集合包含于 $S$ ”，还没保证每个切口真的下降。每份排列都有唯一的真实下降集合，故

\alpha_n(S)=\sum_{T\subseteq S}\beta_n(T).

对这个有限子集和使用容斥可得第二式。也可以直接检查 $\beta_n(U)$ 在右边的总系数：它是 $\sum_{U\subseteq T\subseteq S}(-1)^{|S|-|T|}$ ，只有 $U=S$ 时为一，其余为零。

这里保留整个集合 $S$ 很重要。同样是两个下降，发生在相邻位置还是分散位置，会改变强制递增段的长度，计数也会改变。

例子与边界

要求四元素排列恰在 $S=\{1,3\}$ 下降。四个子集给

\alpha(\{1,3\})=\frac{4!}{1!2!1!}=12, \quad\alpha(\{1\})=4, \quad\alpha(\{3\})=4, \quad\alpha(\varnothing)=1.

因此 $\beta(\{1,3\})=12-4-4+1=5$ ，实际五份是

2143,\quad3142,\quad3241,\quad4132,\quad4231.

它们都呈 $\pi_1>\pi_2<\pi_3>\pi_4$ 。逐个检查为五份，独立核验了容斥结果。

对 $S=\{1,2\}$ ，相邻两次下降强制前三项递减。可直接选最后一个元素；若最后为一则前三项是 $432$ ，末尾也下降，不合要求。最后选 $2,3,4$ 才给 $4312,4213,3214$ ，共三份。公式同样给 $12-4-6+1=3$ 。所以不能只因 $|S|=2$ 就把这两类都计成五。

只指定一个下降位置 $s$ 时， $\beta_n(\{s\})=\binom ns-1$ 。 $n=4$ 的三种位置给 $3,5,3$ ，总和十一，回到 $A(4,1)$ 。这提供从细统计到粗统计的交叉核验。

若把“允许下降”误当“必须下降”，上例会错误得到十二。若排序值有重复，相等位置不属于严格下降，但段内的标签分配不再由同一个多项式系数计算，必须使用多重集版本而非原样照搬。

推论与应用

对所有 $|S|=k$ 求和， $A(n,k)=\sum_{|S|=k}\beta_n(S)$ 。计算某个特定模式时，先保留集合再求和通常比试图从 Eulerian 总数反推位置更有效。

交替排列的数目也可由这个公式计算，但它是 Euler 数而非 Eulerian 数。例如四元素的下降集合固定为 $\{1,3\}$ 时有五份；“两次下降”共有十一份。仅凭中文“欧拉数”容易混淆，应该给出被计数对象。

该方法最坏需要 $2^{|S|}$ 个子集项。若只是要总下降数，Eulerian 的二维递推更省；若要某个下降集合，段长多项式系数加容斥则给精确答案。方法选择取决于要保留哪些信息，不能把更细的模型当作总是更快。

保留逆序权重

同一切口方法还能保留逆序数，定义

\alpha_n(S;q)=\sum_{\operatorname{Des}(w)\subseteq S}q^{\operatorname{inv}(w)},\qquad \beta_n(S;q)=\sum_{\operatorname{Des}(w)=S}q^{\operatorname{inv}(w)}.

用原来的段长 $a_1,\ldots,a_{r+1}$ ，有

\alpha_n(S;q)={n\brack a_1,\ldots,a_{r+1}}_q,\qquad \beta_n(S;q)=\sum_{T\subseteq S}(-1)^{|S|-|T|}\alpha_n(T;q).

右边的$q$ 多项式系数不是凭形式替换得到。把每个递增段选到的标签记下，再从小到大读取标签，并写出它属于第几段，得到段号重排词。原排列中一个跨段逆序 $a>b$ 对应较小标签 $b$ 先被读取、其段号却较大的一对，恰是段号词的一个逆序；段内没有逆序。这个编码可逆且保权，所以第一式成立。第二式对每个权重系数使用原来的子集容斥，证明不变。

例如 $n=4,S=\{1,3\}$ 的五份旧例具有逆序数 $2,3,4,4,5$ ，故

\beta_4(\{1,3\};q)=q^2+q^3+2q^4+q^5.

代一得到五。不要把指数改为主指标而原样照搬：固定这个下降集合时，每份主指标都为 $1+3=4$ ，其多项式是 $5q^4$ 。全排列上的主指标等分布并不保持原下降集合。

参考资料

Richard P. Stanley，Enumerative Combinatorics, Vol. 1，作者第二版书稿，§1.4，式1.31–1.35、Proposition 1.4.1，书稿印页38；§2.2，Example 2.2.4，书稿印页228–229：下降集合的容斥。本页采用求和式，不要求额外学习行列式表达。

形式陈述 ​

保留逆序权重 ​

反向链接

形式陈述

保留逆序权重