车问题(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,研究车问题的主要工具是
车多项式。
考察由n个相异元 作成的任一个
全排列 ( 是由1,2,…,n作成的一个全排列)。在这个排列中,元排在第k位,于是这个排列对应于n个车(象棋中的一种棋子)在n×n棋盘上这样的放置方法:在第行第k列的格子上放一个车。因为 彼此相异且,所以在n×n棋盘上,每一行有且仅有一个车,每一列也有且仅有一个车,也就是说,任何两个车既不同行也不同列。
设n是任一个正整数,从一个n×n棋盘中删去若干个格子后所得的图形称为一个棋盘。设C是任一个棋盘,把个车放在棋盘C上,使得任何两个车既不同行也不同列,k个车在棋盘C上这样的放置方法称为k个车在棋盘C上的一种好布局,以表示k个车在棋盘C上的好布局数,并约定。