-
車問題
鎖定
車問題(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，研究車問題的主要工具是車多項式
[1]
。
- 中文名
- 車問題
- 外文名
- problem of rook
- 所屬學科
- 數學（組合學）
- 簡 介
- 一類棋盤上的組合問題
車問題基本介紹
考察由n個相異元
作成的任一個全排列
(
是由1，2，…，n作成的一個全排列)。在這個排列中，元
排在第k位，於是這個排列對應於n個車(象棋中的一種棋子)在n×n棋盤上這樣的放置方法：在第
行第k列的格子上放一個車。因為
彼此相異且
，所以在n×n棋盤上，每一行有且僅有一個車，每一列也有且僅有一個車，也就是説，任何兩個車既不同行也不同列
[2]
。
設n是任一個正整數，從一個n×n棋盤中刪去若干個格子後所得的圖形稱為一個棋盤。設C是任一個棋盤，把
個車放在棋盤C上，使得任何兩個車既不同行也不同列，k個車在棋盤C上這樣的放置方法稱為k個車在棋盤C上的一種好佈局，以
表示k個車在棋盤C上的好佈局數，並約定
。
車問題例題解析
【例1】對於棋盤C：
圖1
求
。
解：
，當k≥3時，
。
【例2】 證明：對於n×n棋盤C，有
(1)選出k個車所放的k行，有
種方法；
(2)把k個車放在已選出的k行格子上，每行放一個車，且彼此不同列，有
種方法。
由乘法原則，有
