禁位命中数与车变换

形式陈述

给定 $B\subseteq[n]^2$ ，把它看作“被标记的位置”，未必都是必须避免的位置。对排列 $\pi$ 记

h_B(\pi)=|\{i:(i,\pi(i))\in B\}|, \qquad N_j(B)=|\{\pi:h_B(\pi)=j\}|.

在已知车数 $r_k(B)$ 后，全部命中分布由一个平移确定：

H_B(u)=\sum_{j=0}^nN_j(B)u^j =\sum_{k=0}^n r_k(B)(n-k)!(u-1)^k.

所以

N_j(B)=\sum_{k=j}^n(-1)^{k-j}\binom kj r_k(B)(n-k)!,

而反方向是

r_k(B)(n-k)!=\sum_{j=k}^n\binom jkN_j(B).

边界 $k=0$ 给 $\sum_jN_j=n!$ ； $j=0$ 恢复避免全部禁位的容斥式。不要把 $r_j$ 本身误作 $N_j$ ：前者只放 $j$ 个车，后者放满 $n$ 个车并要求恰有 $j$ 个落在 $B$ 。

直觉

先数一个更容易的对象：一份完整排列，再从它命中的格子里圈出 $k$ 格。若排列一共命中 $j$ 格，可以圈出 $\binom jk$ 种不同的证据；因此按完整排列分类，圈选对的数量是 $\sum_j\binom jkN_j$ 。

改为先选圈出的格子。它们必须是一组非攻击车，有 $r_k$ 种；把其余行列补满有 $(n-k)!$ 种。于是同一批“排列加圈选证据”给出逆方向等式。这是握手计数中“先固定被关联的一侧”思想的迁移，数的对象不再是端点，而是一个被标记的子配置。

将这个等式乘 $t^k$ 后求和，用二项式定理得到

\sum_k r_k(n-k)!t^k =\sum_jN_j\sum_k\binom jk t^k =H_B(1+t).

再令 $t=u-1$ 即得主公式。所有多项式都是有限的，因此这里不存在无限换序或收敛问题。

例子与边界

对禁位板 $\{(1,1),(1,2),(2,2),(3,3),(4,4)\}$ ，车多项式给 $(r_0,\ldots,r_4)=(1,5,8,5,1)$ 。因此

\begin{aligned} 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{aligned}

逐阶展开可检查 $u^2$ 系数： $16-3\cdot5+6=7$ 。恰命中三格的排列只能是 $2134$ ，恰命中四格的是 $1234$ ；这两项在板上直接可见。零命中的六项在车多项式页列全。

反向核验 $k=2$ 不再重复同一种展开：

\binom22\cdot7+\binom32\cdot1+\binom42\cdot1 =7+3+6=16=r_2\,2!.

此外 $H_B(1)=24$ ； $H_B'(1)=30$ ，也等于五个标记格子各被 $3!=6$ 份排列占用所得的总命中次数。

若 $B=\{(1,1),(1,2)\}\subseteq[2]^2$ ，两个排列都恰命中一格，故 $H_B(u)=2u$ 。虽然 $r_1=2$ ，却没有任何能同时圈中两格的排列， $r_2=0$ 。因此“有两个被标记位置”不意味着可能有两次命中。

由任意非负系数多项式冒充车多项式也可能失败。例如假设 $n=2,r=(1,3,0)$ ，变换给 $H(u)=2+3(u-1)=-1+3u$ ，出现负计数，证明这组数据不可能来自真正的两行两列棋盘。

推论与应用

对于对角板，恰有 $j$ 个固定点的排列数是 $\binom njD_{n-j}$ ：先选固定点，再在剩下的位置做错排。这提供了命中公式的独立校验，而不是另建一页近名“固定点计数”。

命中多项式还能帮助比较两块限制不同的棋盘：在同一个 $n$ 下，它们具有相同车数，当且仅当具有相同命中数，因为 $u\leftrightarrow1+t$ 可逆。但这只比较计数，不给逐个合法安排之间的自然双射，也不说明棋盘必可由换行、换列互相得到。

给车放置加权时必须重做“双计数的剩余完成”一步。若每个完整排列的权重依赖于其全部位置，剩余行列的权重和通常不是 $(n-k)!$ ；不能只把 $r_k$ 换成任意加权系数就宣称公式原样成立。

参考资料

Richard P. Stanley，Enumerative Combinatorics, Vol. 1，作者第二版书稿，§2.3，Theorem 2.3.1 及两份证明，书稿印页231–232。本页使用“完整排列加选中的命中子集”的双计数版本。
NIST DLMF，§26.15，式26.15.6–8：命中多项式与普通车多项式的平移关系。