车问题
棋盘上的组合问题
车问题(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上的好布局数,并约定。
例题解析
【例1】对于棋盘C:
求。
解:,当k≥3时,。
【例2】 证明:对于n×n棋盘C,有
证明:可依如下两个步骤去完成k个车在C上的好布局:
(1)选出k个车所放的k行,有 种方法;
(2)把k个车放在已选出的k行格子上,每行放一个车,且彼此不同列,有 种方法。
由乘法原则,有
参考资料
最新修订时间:2022-09-24 17:18
目录
概述
基本介绍
例题解析
参考资料