棋盘多项式

组合数学的核心是解决计数问题，其中很重要的即为n个元素的排列方案的计数。一个常见的将排列问题抽象的方法就是将其抽象为棋盘多项式。首先看一个 $n \times n$ 的棋盘，n个元素的排列可以看成在这个棋盘上落下n个棋子，其中每一个横行、每一个竖列只允许有一个棋子。而其中棋盘的格子是可以任意的 $n \times n$ 的棋盘的子集，这对应了存在一定限制的排列方案。

每一个棋盘对应着一个母函数代表该棋盘中描述无法攻击的棋子排列数。这个母函数即为棋盘多项式。

棋盘多项式

定义

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

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

性质

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

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

应用

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

受限排列

定理

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

定理证明

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

\begin{matrix} | \overline{A_{1}} \cap \overline{A_{2}} \cap \overline{A_{3}} \cap \dots \cap \overline{A_{n}} | = & | \overline{A_{1} \cup A_{2} \cup A_{3} \cup \dots \cup A_{n}} | \\ = & n! - | A_{1} \cup A_{2} \cup A_{3} \cup \dots \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} | + \dots + (- 1)^{n - 1} | A_{1} \cap A_{2} \cap \dots \cap A_{n} |) \end{matrix}

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

举例

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

		×
×			×
	×		×
	×

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

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

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

参考文献

↑ Template:Cite book

Template:Authority control

[1] Template:Cite book

[1]

棋盘多项式

目录