車問題(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，若Ai={j|a'ij=0，1≤j≤n}，i=1，2，…，m，則{A1，A2，…，Am}是集合{1，2，…，n}的子集族，{A1，A2，…，Am}的關聯矩陣就是一個(A1，A2，…，Am)限位排列的關聯矩陣，m個車在與棋陣A'(a'ij)相應的棋盤B上的布陣數，等於(A1，A2，…，Am)限位排列總數N0(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行格子上，每行放一個車，且彼此不同列，有
種方法。
由乘法原則，有
