车多项式与禁位排列

把“第 $i$ 个位置不得放 $j$”画成格子，比把几十条限制写成句子更容易发现冲突。容斥会暂时强迫若干禁令同时被违反。若强迫同一行放两个不同元素，或强迫两行使用同一元素，交集就是空集；剩下可实现的交集，正好是一组互不攻击的车。

删占递推按 $s$ 是否被选分两类。不选者恰是 $B-s$ 上的放置；选者拿掉 $s$ 上的车后，剩余车必须避开整行整列。这个拆法可逆，且不选与选互斥，所以系数可以相加。占用一格使车数增加一，因此要乘 $t$。

分块乘积来自同样清楚的双射：把一个放置分别限制在 $B_1,B_2$ 上，得到两个可独立选择的放置；反向取并集也不会攻击。于是 $r_k(B)=\sum _{a+b=k}{r}_a(B_1)r_b(B_2)$，这就是多项式乘法。

为什么最后还要乘阶乘 ​

对每个禁位 $s=(i,j)$，令 $A_s=\{\pi :\pi (i)=j\}$。由容斥原理理路容斥原理Inclusion–exclusion principle · PIE通过交集的交替和修正多个有限集合并集的重复计数。，避免全部 $A_s$ 的数目是所有交集大小的交替和。选出的 $k$ 格若攻击，交集大小为零；若不攻击，已确定 $k$ 个不同输入的不同像，剩余 $n-k$ 个输入与 $n-k$ 个像可任意双射，恰有 $(n-k)!$ 个完成。因此同阶非零交集合并成 $r_k(B)(n-k)!$。

这里的剩余排列仍允许再次命中其他禁位。容斥本来就是在无约束总体里算交集；若提前删掉其他禁位，会重复施加排除条件。

取四行四列禁位

左上三格组成 $L$ 块，其车数为 $r_0=1,r_1=3,r_2=1$；唯一两车放置是 $\{(1,1),(2,2)\}$。另外两格各占独立行列，所以

第二项之后可逐项核对：两车数 $1+3\cdot 2+1=8$；三车数 $1\cdot 2+3\cdot 1=5$；四车数为一。于是

独立枚举不使用车多项式：第一行只能取 $3$ 或 $4$。取 $3$ 时合法列表是 $3142,3412,3421$；取 $4$ 时是 $4123,4312,4321$。六个列表都把第 $i$ 项解释为 $\pi (i)$。

两个单格 $(1,1),(1,2)$ 虽然不相交，却共行。其多项式是 $1+2t$，不是 $(1+t{)}^2$。对角禁位则确实独立，得到 $(1+t{)}^n$，代入上式恢复旧错排理路错排Derangement没有任何元素停留在原位置的置换及其计数问题。公式，不需要另造一种错排定义。

空棋盘的多项式是 $1$，并非零；它给 $n!$ 个合法排列。满 $n\times n$ 禁位板在 $n>0$ 时不给任何合法排列。矩形板仍能统计部分车，但最后的 $(n-k)!$ 公式声明的是方阵上的全排列；若要把 $m$ 人注入 $n$ 个岗位，$m\le n$ 时应改用 $(n-k{)}^{\underset{―}{m-k}}=(n-k)(n-k-1)\cdots (n-m+1)$ 个完成（零个因子时为一）。

完整矩形板上先选 $k$ 行、$k$ 列，再把它们配对，得到 $r_k=(\genfrac{}{}{0ex}{}{m}{k})(\genfrac{}{}{0ex}{}{n}{k})k!$。这也说明车多项式是对应二分图按大小计数的匹配多项式的一种编码，但本页不替代匹配存在性、增广路或指派最优化的现有正本。

若要计“恰违反两条”，只算 $N_0$ 已经丢失信息，应使用命中数变换理路禁位命中数与车变换Rook hit numbers · Hit polynomial从部分禁位放置恢复恰命中j格的完整排列数，并用双计数、平移多项式和逆变换交叉核验。。若行或列按高度逐层嵌套，Ferrers 车因式分解理路Ferrers 棋盘的阶乘因式分解Ferrers rook factorization · Factorial rook polynomial · Goldman–Joichi–White factorization以嵌套行的双计数证明阶乘车多项式线性分解，算出阶梯板车数并构造集合划分的弧编码。可以把同一个多项式改写到阶乘基后快速求系数。

删占递推总能用于有限板，却可能产生指数多个分支。它是正确性可检查的算法，不是任意禁位计数都高效的承诺。实际计算可先拆互不共行列的连通块，再缓存重复子板。