从禁位安排到排列统计 ​

四个不同的人分别占据四个有编号的位置，每人、每位各用一次。把第 $i$ 位安排的人记为 $\pi (i)$，于是安排是一个排列。本页中的所有计数均为精确整数，空排列算一份；下降不包含最后位置，也不把末项与首项环接。

先选一条能走到底的路 ​

• 想解决禁位安排：排列理路排列Permutation有限集合到自身的双射，或其元素的有序排列。 → 容斥理路容斥原理Inclusion–exclusion principle · PIE通过交集的交替和修正多个有限集合并集的重复计数。 → 车多项式理路车多项式与禁位排列Rook polynomial · 禁位棋盘计数把兼容的禁位交集编码为非攻击车，证明删占递推、独立分块乘积和禁位排列的容斥公式。 → 命中数理路禁位命中数与车变换Rook hit numbers · Hit polynomial从部分禁位放置恢复恰命中j格的完整排列数，并用双计数、平移多项式和逆变换交叉核验。。这条短路完成任务一、二，不必先学后面的换基
• 想理解同一批排列为何有不同数表：循环数理路第一类 Stirling 数Unsigned Stirling number of the first kind · Signed Stirling number of the first kind · 循环数以可逆的循环插入证明第一类Stirling递推，区分有符号和无符号约定，复算四阶全表与循环型。与下降数理路Eulerian 数与排列下降Eulerian number · Eulerian polynomial · 排列下降数以插入最大元素证明下降数递推，推导Eulerian多项式并用n=4分位置核验十一项。 → 指定下降位置理路排列下降集合的精确计数Descent-set enumeration · Exact descent set · MacMahon descent-set formula先数下降只能出现在指定切口的排列，再用子集容斥恢复恰好下降集合，区分位置统计与下降总数。 → 循环与纪录双射理路Foata 基本变换Foata fundamental transformation · Fundamental bijection on permutations通过标准循环书写与纪录位置切分构造互逆双射，证明循环数对应纪录数、下降数对应亏位并迁移到超越统计。；Lehmer码理路排列逆序编码与字典序编号Lehmer code · Permutation ranking and unranking · Inversion code用右侧较小元素数构造排列的混合进位码，证明确定性编解码和字典序rank/unrank，再复用逆序生成乘积。是可选的逐项核验分支。完成任务三、四
• 想把表格变成可迁移代数：复用第二类Stirling理路第二类 Stirling 数Stirling number of the second kind把 n 元集合划分为 k 个非空无标号块的方案数。 → 阶乘换基理路升降阶乘与 Stirling 换基Falling factorial basis · Rising factorial · Stirling inversion在特征零多项式中建立普通幂、下降阶乘、上升阶乘三组坐标，以计数和三角性证明两类Stirling互逆。 → 差分与离散求和理路有限差分的离散微积分Calculus of finite differences · Newton forward expansion · 前向差分算子用前向差分恢复多项式、判定整数格上的次数，并通过二项式基求离散原函数和幂和。，再选择整值证书理路整值多项式与二项式基Integer-valued polynomial · Binomial polynomial basis用有限差分证明有理多项式在所有整数上取整数的判据，并区分整值与整系数、有限样本与次数证书。、线性有序块理路Lah 数与线性有序块Unsigned Lah numbers · List partition numbers区分块内线性顺序与块间无序，证明Lah闭式和插入递推，再连接升降阶乘和两类Stirling数。、阶梯棋盘理路Ferrers 棋盘的阶乘因式分解Ferrers rook factorization · Factorial rook polynomial · Goldman–Joichi–White factorization以嵌套行的双计数证明阶乘车多项式线性分解，算出阶梯板车数并构造集合划分的弧编码。与稳定排序幂展开理路Worpitzky 恒等式与幂的下降展开Worpitzky identity · Eulerian power identity用稳定排序把任意函数唯一分到下降模式，证明Worpitzky展开并推导幂和有理生成函数、Eulerian显式式与EGF。。完成任务五至七

二项式反演理路二项式反演与序列变换Binomial inversion · Binomial transform证明二项式三角变换的显式逆，并分别推导OGF代换和EGF乘法，说明按大小合并的对称性前提。说明差分与容斥共享的三角消去，但不是学习车多项式前必须走的绕路。末站Worpitzky使用二项式系数理路二项式系数Binomial coefficientn 元集合的 k 元子集数，记作 C(n,k)。与隔板法理路隔板法Stars and bars把相同对象分入有标号盒子的整数解计数方法。，可在需要时回读；Ferrers分支先读车多项式。原有 Catalan、Burnside/Pólya与匹配算法仍有各自的计数对象，不把它们改名纳入本页。

任务一：五个禁位为什么留下六份安排 ​

输入固定为

$$B=\{(1,1),(1,2),(2,2),(3,3),(4,4)\}\subseteq [4{]}^2.$$

输出需要三份证据：车数 $r_0,\dots ,r_4$、容斥结果、全部合法列表。先暂停，试着亲自找出左上角三格能否放两辆车。

左上块 $L$ 的三格中，只有 $(1,1)$ 与 $(2,2)$ 可以同时占用。故 $R_L=1+3t+t^2$。两个单格与它不共行列，也互不共行列，得到

$$R_B=(1+3t+t^2)(1+t{)}^2=1+5t+8t^2+5t^3+t^4.$$

再独立直接数二车：五格共有 $(\genfrac{}{}{0ex}{}{5}{2})=10$ 对，冲突对只有同行的 $\{(1,1),(1,2)\}$ 与同列的 $\{(1,2),(2,2)\}$，所以二车数为八。三车按是否选两个独立单格分类：二者都选则左上选一格，贡献三；只选其中一个则左上必须放两车，贡献二，总计五。四车只能沿主对角线，贡献一。

容斥对每个禁格先强迫它被占用。同阶非空交集对应非攻击车，选好 $k$ 格后仍有 $(4-k)!$ 个无约束完成，所以

$$N_0=4!-5\cdot 3!+8\cdot 2!-5\cdot 1!+0!=24-30+16-5+1=6.$$

逐项枚举不用这条公式：第一项只能为三或四。若为三，分别按第二项尝试一、二、四；二被禁，余下得到 $3142,3412,3421$。若为四，同理得到 $4123,4312,4321$。六份中每项都互异，且第三项非三、第四项非四，核验通过。

任务二：把“合法或不合法”细分到命中次数 ​

输入仍为 $B$，这次输出恰命中 $j$ 个禁位的完整分布，而非只输出零命中。圈出排列命中的任意 $k$ 格，双计数给

$$\sum _{j=k}^4(\genfrac{}{}{0ex}{}{j}{k})N_j=r_k(4-k)!.$$

所以命中多项式为

$$\begin{array}{rl}{H}_B(u)& =24+30(u-1)+16(u-1{)}^2+5(u-1{)}^3+(u-1{)}^4\\ & =6+9u+7u^2+u^3+u^4.\end{array}$$

答案是 $(N_0,N_1,N_2,N_3,N_4)=(6,9,7,1,1)$。总和二十四；总命中数 $9+2\cdot 7+3+4=30$，也等于五个格各有 $3!$ 个占用排列。二阶圈选总数为 $7+3+6=16$，也等于 $r_{2}2!$。

以下表格逐项给出四元素排列的全部数据。$c$ 为循环数，$d$ 为下降数，$I$ 为逆序对数，$h$ 为对本题 $B$ 的命中数。可以用字典序从 $1234$ 枚到 $4321$，每份恰出现一次。

排列	$c$	$d$	$I$	$h$
$1234$	4	0	0	4
$1243$	3	1	1	2
$1324$	3	1	1	2
$1342$	2	1	2	1
$1423$	2	1	2	1
$1432$	3	2	3	2
$2134$	3	1	1	3
$2143$	2	2	2	1
$2314$	2	1	2	2
$2341$	1	1	3	1
$2413$	1	1	3	1
$2431$	2	2	4	2
$3124$	2	1	2	1
$3142$	1	2	3	0
$3214$	3	2	3	2
$3241$	2	2	4	1
$3412$	2	1	4	0
$3421$	1	2	5	0
$4123$	1	1	3	0
$4132$	2	2	4	1
$4213$	2	2	4	1
$4231$	3	2	5	2
$4312$	1	2	5	0
$4321$	2	3	6	0

任务三：重新推导三张四阶数表 ​

第一类看循环。最大标签四若单独成循环，来自三元素的少一个循环；否则插入任一旧箭头，有三个位置。所以

$$c(4,k)=c(3,k-1)+3c(3,k).$$

第三行非零项是 $(2,3,1)$，逐项得第四行 $(6,11,6,1)$。循环型独立校验：一个四循环六份；三循环加固定点八份、双二循环三份，共十一份二循环对象；一个二循环加两固定点六份；全固定一份。

第二类看无序非空块。四若自己成块，来自三元素少一个块；否则加入已有 $k$ 块之一，所以

$$S(4,k)=S(3,k-1)+kS(3,k).$$

第三行是 $(1,3,1)$，第四行是 $(1,7,6,1)$。七份二块划分是

$$1|234,2|134,3|124,4|123,12|34,13|24,14|23.$$

竖线两边交换不创造新划分。三块划分只能选出唯一的二元素块，所以有 $(\genfrac{}{}{0ex}{}{4}{2})=6$ 份。

Eulerian 数看相邻下降。插入最大元四到已有下降缝或末尾，下降数保持不变；插到上升缝或最前，增加一个。因此

$$A(4,k)=(k+1)A(3,k)+(4-k)A(3,k-1).$$

第三行 $(1,4,1)$ 给第四行 $(1,11,11,1)$。恰一个下降再按位置细分为 $3,5,3$，不是均匀的十一除以三。恰在位置 $1,3$ 下降的五份为 $2143,3142,3241,4132,4231$，与 $12-4-4+1=5$ 的下降集合容斥一致。

三张数表数的对象不同：第二类的总和为十五个集合划分；第一类与Eulerian各总和二十四，因为都在分类排列。数字相近不能证明对象相同。

任务四：把一份排列来回转换 ​

取 $\sigma =(123)(45)$。先让每循环最大元在首位，再按这些最大元递增排列，得到 $(312)(54)$。擦括号为 $31254$，纪录为三、五，所以两条纪录恢复两个循环。下降为 $3>1$、$5>4$，恰对应原映射的两条亏位箭头。

若要把超越变成下降，应用的是 $\pi \mapsto F({\pi }^{-1})$；$F(\sigma )$ 自身对应亏位，不能省去取逆。回读 $31254$ 时在纪录前切为 $312|54$，证明这一步确实可逆。

另对四元素的合法安排 $3142$ 求 Lehmer码。每位右侧较小元素数为 $(2,0,1,0)$，编号为 $2\cdot 6+0\cdot 2+1\cdot 1=13$，从零编号。反向从十三做阶乘除法恢复同一码，再从未用列表依次选第三、第一、第二、第一小，恢复 $3142$。逆序数是码位总和三，却不足以唯一标识排列。

任务五：阶梯棋盘把三张表接起来 ​

换输入为四阶阶梯板

$$T=\{(i,j):1\le j<i\le 4\},(b_1,b_2,b_3,b_4)=(0,1,2,3).$$

Ferrers因式分解给 $F_T(x)=x^4$。把它写成下降阶乘基，

$$x^4=x^{\underset{―}{4}}+6x^{\underset{―}{3}}+7x^{\underset{―}{2}}+x,$$

所以 $R_T(t)=1+6t+7t^2+t^3$。这恰是 $r_k=S(4,4-k)$，位置倒序是因为放一辆车把递增弧路径的块数减少一。

车到集合划分可以直接核验：把车 $(i,j)$ 画成 $j\to i$，得到互不分叉的递增路径，路径顶点集就是块。譬如划分 $\{1,3,4\}|\{2\}$ 给两车 $(3,1),(4,3)$。反向把每块排序相连恢复车。因此车数与Stirling的对应有实际双射，绝不只靠多项式前几项相同。

命中变换现在给

$$H_T(u)=24+36(u-1)+14(u-1{)}^2+(u-1{)}^3=1+11u+11u^2+u^3.$$

命中阶梯板意味着 $\pi (i)<i$，即亏位数。Foata基本变换把亏位送到下降，所以命中多项式必等于 $A_4(u)$。这里“棋盘容斥”“集合划分换基”“排列双射”三条独立结构终于得到同一个答案。

任务六：从四次表格推回多项式与幂和 ​

输入是已知次数不超过四、在 $0,1,2,3,4$ 取 $0,1,16,81,256$ 的多项式。左端差分为 $0,1,14,36,24$，故

$$p(x)=(\genfrac{}{}{0ex}{}{x}{1})+14(\genfrac{}{}{0ex}{}{x}{2})+36(\genfrac{}{}{0ex}{}{x}{3})+24(\genfrac{}{}{0ex}{}{x}{4})=x^4.$$

系数 $14,36,24$ 除以 $2!,3!,4!$ 后成为 $7,6,1$，与第二类数一致。离散求和让下标增加一：

$$\sum _{m=0}^{N-1}{m}^4=(\genfrac{}{}{0ex}{}{N}{2})+14(\genfrac{}{}{0ex}{}{N}{3})+36(\genfrac{}{}{0ex}{}{N}{4})+24(\genfrac{}{}{0ex}{}{N}{5}).$$

$N=5$ 时为 $10+140+180+24=354$，也等于 $0+1+16+81+256$。

另一种展开用下降数，而非块数：Worpitzky给

$$2^4=(\genfrac{}{}{0ex}{}{5}{4})+11(\genfrac{}{}{0ex}{}{4}{4})+11(\genfrac{}{}{0ex}{}{3}{4})+(\genfrac{}{}{0ex}{}{2}{4})=5+11=16.$$

两式使用不同的二项式基，不能把 $7$ 与 $11$ 随意替换。生成函数中，四次幂的OGF为

$$\sum _{m\ge 0}{m}^4{t}^m=\frac{t(1+11t+11t^2+t^3)}{(1-t{)}^5}.$$

例如 $t^2$ 系数为 $5+11=16$，$t^3$ 系数为 $15+55+11=81$。这又把Eulerian系数与直接幂值相连。

任务七：两项可选的进一步迁移 ​

整值证书：次数至多三，四个连续整数上的值为 $1,2,5,11$。Newton系数是 $1,1,2,1$，所以

$$p(x)=1+(\genfrac{}{}{0ex}{}{x}{1})+2(\genfrac{}{}{0ex}{}{x}{2})+(\genfrac{}{}{0ex}{}{x}{3})$$

在所有整数上取整数，虽然普通幂系数有分母六。负数测试 $p(-2)=1$；下一点 $p(4)=21$。若不声明次数界，有限采样无法排除再加一个在已知节点消失的高次多项式。

列表块迁移：四个标签分成两个无序、内部有线性顺序的非空块，切长列表并忘掉块序得到 $L(4,2)=4!(\genfrac{}{}{0ex}{}{3}{1})/2!=36$。先作循环再作集合划分的换基卷积也给 $11\cdot 1+6\cdot 3+1\cdot 7=36$。这不是第一类或第二类数的误差，而是第三种块结构。

失败边界与交卷检查 ​

• 车的分块只在行与列都不共用时独立；两格 $(1,1),(1,2)$ 给 $1+2t$，不会产生 $t^2$
• 禁位板与允许板不能混用。容斥的交集在完整排列总体里计数，未固定的位置仍允许命中其他禁位
• 命中数 $N_j$ 计满排列，车数 $r_j$ 计部分放置，两者相差的不仅是一个阶乘
• 第一类反演使用有符号 $s(n,k)$。无符号替代会把应为零的矩阵项算成36
• Foata必须先标准化循环；按本页约定它将亏位送到下降，超越对应需先取逆
• 差分判次需要全格恒等式，或预先给定次数界。有限表格与任意实变量函数之间没有自动唯一性
• OGF与EGF有不同的系数规范；形式等式不授权在任意数值点求和，EGF分母中的阶乘还要求系数环允许除法

能交出所选路线对应的中间对象与反例，才算完成这条路线。最后的数字六只是最短答案，棋盘、插入操作、可逆编码和换基证书才使方法能搬到下一题。

资料与复核入口 ​

• 车多项式理路车多项式与禁位排列Rook polynomial · 禁位棋盘计数把兼容的禁位交集编码为非攻击车，证明删占递推、独立分块乘积和禁位排列的容斥公式。与命中数理路禁位命中数与车变换Rook hit numbers · Hit polynomial从部分禁位放置恢复恰命中j格的完整排列数，并用双计数、平移多项式和逆变换交叉核验。列出完整定理、证明和源节
• Richard P. Stanley，Enumerative Combinatorics, Vol. 1，作者第二版书稿，§§1.3–1.4、1.9、2.1、2.3–2.4：排列统计、差分和禁位主线
• NIST DLMF，§26.8、§26.14、§26.15：两类Stirling、零下降约定与命中多项式的独立表式校准