車問題

車問題(problem of rook)是一類棋盤上的組合問題，設B是一個由m行n列的方格組成的廣義棋盤，B上有一些禁用格，其餘均為可用格，車問題是：將k只象棋棋子車按下列規則分布在棋盤B上，使得：1.每個車放在一個可用格上；2.任意兩個車不在同一行或同一列上；問不同的分布數是多少?一個與給定的棋盤B相聯繫的m×n(0，1)矩陣A'(a'_ij)稱為是一個棋陣，這裡，當B的位於第i行、j列的方格為禁用格時，a'_ij=1；而當B的位於第i行、j列的方格為可用格時，a'_ij=0，若A_i={j|a'_ij=0，1≤j≤n}，i=1，2，…，m，則{A₁，A₂，…，A_m}是集合{1，2，…，n}的子集族，{A₁，A₂，…，A_m}的關聯矩陣就是一個(A₁，A₂，…，A_m)限位排列的關聯矩陣，m個車在與棋陣A'(a'_ij)相應的棋盤B上的布陣數，等於(A₁，A₂，…，A_m)限位排列總數N₀(m，n)=per A，研究車問題的主要工具是車多項式。

基本介紹

• 中文名：車問題
• 外文名：problem of rook
• 所屬學科：數學（組合學）
• 簡介：一類棋盤上的組合問題

基本介紹

考察由n個相異元 作成的任一個全排列 ( 是由1，2，…，n作成的一個全排列)。在這個排列中，元排在第k位，於是這個排列對應於n個車(象棋中的一種棋子)在n×n棋盤上這樣的放置方法：在第行第k列的格子上放一個車。因為 彼此相異且，所以在n×n棋盤上，每一行有且僅有一個車，每一列也有且僅有一個車，也就是說，任何兩個車既不同行也不同列。

設n是任一個正整數，從一個n×n棋盤中刪去若干個格子後所得的圖形稱為一個棋盤。設C是任一個棋盤，把個車放在棋盤C上，使得任何兩個車既不同行也不同列，k個車在棋盤C上這樣的放置方法稱為k個車在棋盤C上的一種好布局，以表示k個車在棋盤C上的好布局數，並約定。

例題解析

【例1】對於棋盤C：

圖1

求。

解：，當k≥3時，。

【例2】 證明：對於n×n棋盤C，有

證明：可依如下兩個步驟去完成k個車在C上的好布局：

(1)選出k個車所放的k行，有 種方法；

(2)把k個車放在已選出的k行格子上，每行放一個車，且彼此不同列，有 種方法。

由乘法原則，有