棋盘多项式

定义

设C为一棋盘，称${\displaystyle \sum _{k=0}^{n}{r_{k}}(C){x^{k}}}$ 为C的棋盘多项式，其中${\displaystyle {r_{k}}(C)}$ 表示k个棋子布到棋盘C的方案数^[1]。

• 规定${\displaystyle {r_{0}}(C)=1}$ 

性质

• 设${\displaystyle {C_{i}}}$ 是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘，${\displaystyle {C_{e}}}$ 是仅去掉该格子后的棋盘，则${\displaystyle {r_{k}}(C)={r_{k-1}}({C_{i}})+{r_{k}}({C_{e}})}$ 

• 如果${\displaystyle {C}}$ 由相互分离的${\displaystyle {C_{1}}}$ 和${\displaystyle {C_{2}}}$ 组成，即${\displaystyle {C_{1}}}$ 的任一格子所在的行和列中都没有${\displaystyle {C_{2}}}$ 的格子，则有${\displaystyle {r_{k}}(C)=\sum _{i=0}^{k}{r_{i}}({C_{1}}){r_{k-i}}({C_{2}})}$ 

应用

结合容斥原理解决受限排列问题。

定理

设${\displaystyle {r_{i}}}$ 为 i个棋子布入禁区的方案数，i =1,2,3,…,n。有禁区的布子方案数（即禁区内不布棋子的方案数）为 ${\displaystyle {n!}-{r_{1}}{(n-1)!}+{r_{2}}{(n-2)!}-...+{(-1)^{n}}{r_{n}}}$ 

定理证明

设事件${\displaystyle A_{i}}$ 为棋子${\displaystyle i}$ 落入禁区且其余棋子不限定是否落入禁区。 那么布子方案数即可用${\displaystyle |{\overline {A_{1}}}\cap {\overline {A_{2}}}\cap {\overline {A_{3}}}\cap \cdots \cap {\overline {A_{n}}}|}$ 进行表示。该排列数可以用容斥原理求解。 即${\displaystyle |{\overline {A_{1}}}\cap {\overline {A_{2}}}\cap {\overline {A_{3}}}\cap \cdots \cap {\overline {A_{n}}}|=|{\overline {A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n}}}|}$  其中，在棋盘上的不受限排列数为${\displaystyle n!}$ ，那么有

${\displaystyle {\begin{aligned}|{\overline {A_{1}}}\cap {\overline {A_{2}}}\cap {\overline {A_{3}}}\cap \cdots \cap {\overline {A_{n}}}|=&|{\overline {A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n}}}|\\=&n!-|A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n}|\\=&n!-(\sum _{i=1}^{n}|A_{i}|-\sum _{i=1}^{n}\sum _{j>i}|A_{i}\cap A_{j}|+\sum _{i=1}^{n}\sum _{j>i}\sum _{k>j}|A_{i}\cap A_{j}\cap A_{k}|+\cdots +(-1)^{n-1}|A_{1}\cap A_{2}\cap \cdots \cap A_{n}|)\end{aligned}}}$ 

其中，至少有一个棋子落入禁区的方案数为${\displaystyle \sum _{i=1}^{n}|A_{i}|={r_{1}}(n-1!)}$ ，至少两个棋子落入进去的方案数为${\displaystyle |\sum _{i=1}^{n}\sum _{j>i}A_{i}\cap A_{j}|={r_{2}}(n-2!)}$ ，以此类推，可以得到等式 ${\displaystyle |{\overline {A_{1}}}\cap {\overline {A_{2}}}\cap {\overline {A_{3}}}\cap \cdots \cap {\overline {A_{n}}}|={n!}-{r_{1}}{(n-1)!}+{r_{2}}{(n-2)!}-...+{(-1)^{n}}{r_{n}}}$ 

举例

1.如下图所示，在${\displaystyle 4\times 4}$ 的棋盘上，打叉的地方为禁区，求棋子无一落入禁区的排列数。

首先通过排列多项式的性质得到禁区的棋盘多项式为${\displaystyle 1+6x+11x^{2}+7x^{3}+x^{4}}$ 。 这样，该棋盘在受限情况下的方案数为${\displaystyle 4!-6\times 3!+11\times 2!-7\times 1!+1=4}$ 。

2.错排问题，即${\displaystyle n}$ 个元素组成的排列中标号为${\displaystyle i}$ 的元素不排在第${\displaystyle i}$ 位的方案数。

该问题即为受限排列问题。 具体到棋盘中，即为在${\displaystyle n\times n}$ 的棋盘上，所有的对角线元素都是禁区。 对于禁区的棋盘多项式的计算，由于该棋盘中所有元素均不在同一行同一列，根据棋盘多项式的性质容易得到为${\displaystyle (1+x)^{n}}$ 。 那么，根据受限排列的性质，得到错排方案数为${\displaystyle n!-C(n,1)(n-1)!+C(n,2)(n-2)!+\cdots +(-1)^{n-1}C(n,n)}$ 。

• 组合数学
• 容斥原理
• 错排问题