車多項式

車多項式(rook polynomials)是美國數學家John Riordan在研究西洋棋中車的禁位排列問題時創立的多項式。設B為n個對象受限制的排列問題的棋盤，r_k(B)(k=1，2，…，n)是B的不同行不同列中取k個小暗方塊的不同方法的數目，則稱多項式R(x，B)=1+r₁(B)x+r₂(B)x+…+r_n(B)x為B的車多項式。

基本介紹

• 中文名：車多項式
• 外文名：rook polynomials
• 所屬學科：數學（組合學）
• 簡介：是研究棋陣問題的主要工具

基本介紹

車多項式是研究棋陣問題的主要工具，x的多項式

稱為以矩陣=(_ij)為棋陣的車多項式，這裡，表示k只車分布到與棋陣相應的棋盤B上的不同的分布數，約定，當k大於棋盤B上的可用格個數時，=0，於是，)是一個x的多項式，若在棋陣中任選一個可用格a，把該可用格換為禁用格而其他格不變所得的棋陣記為，把該可用格所在行和列都刪去所得出的一個棋陣記為，則按棋陣之可用格a的展開式是

反覆利用對可用格的展開式，可將的計算歸納為一些已知的或易算的車多項式的計算。

相關定理

下文設C是任一個棋盤，令

則R(t，C)稱為棋盤c的車多項式。

求棋盤車多項式的一般方法是：把求較大的棋盤的車多項式的問題轉化成去求較小的棋盤的車多項式。

為簡便計，在不會引起誤會的情況下，常把簡寫成R(t)，把r_k(C)簡寫成r_k。

定理1 設a是棋盤C上的任一個格子，以C'_a表示從C中去掉與a同行或同列的全部格子後所得的棋盤，以C_a表示從C中去掉格子a後所得的棋盤，則

證明：個車在G上的種好布局可分成如下兩類：

(1)有一個車放在a上的好布局，因為其餘k-1個車放在C'_a上，所以屬於此類的好布局有種。

(2)沒有車放在a上的好布局．因為k個車全部放在C_a上，所以屬於此類的好布局有種。

由加法原則，有

所以

定理2 設C₁和C₂都是棋盤C的子棋盤，C由C₁和C₂拼成，且C₁和C₂彼此分離，即C₁中的任一格子與C₂中的任一格子在C上既不同行也不同列，則