棋盤多項式

組合數學的核心是解決計數問題，其中很重要的即為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的方案數。

• 規定${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 \cdots \cap {\overline {A_{n}}}|$進行表示。該排列數可以用容斥原理求解。 即$|{\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!$，那麼有

${\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}}$

其中，至少有一個棋子落入禁區的方案數為$\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 \cdots \cap {\overline {A_{n}}}|={n!}-{r_{1}}{(n-1)!}+{r_{2}}{(n-2)!}-...+{(-1)^{n}}{r_{n}}$

舉例

1.如下圖所示，在$4\times 4$的棋盤上，打叉的地方為禁區，求棋子無一落入禁區的排列數。

		×
×			×
	×		×
	×

首先通過排列多項式的性質得到禁區的棋盤多項式為$1+6x+11x^{2}+7x^{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)!+\cdots +(-1)^{n-1}C(n,n)$。

相關頁面

• 組合數學
• 容斥原理
• 錯排問題