1、3.5 一般有限制的排列3.3节中的错排问题是一种有限制的排列，即 i不排在第 i位的排列。更一般地若 i不排在某些位的 1，2， ,n 的全排列，其排列个数又如何计算呢 ?此类问题的解法之一是利用所谓 “棋子多项式 ”。设 n是一个正整数，一个 nn 棋盘是指一个正方形被均分为 nn 个小方格所成的 “ 图形 ” 。一个 nn棋盘去掉某些格后剩下部分也称它为一个棋盘。在给定棋盘 C中放入 k个无区别的棋子，要求每个棋子只能放一格，且各子不同行不同列，记不同的放法数为 rk(C)，问 rk(C)=?此问题称为 棋子问题 。例如图 3.3是四个棋子放入55棋盘的一种放法。例 1 设 C1= ,
2、C2= , C3= 有 r1(C1) =r1( )=1,r2( )=0r1(C2) =r1( )=2,r2( )=0r1(C3) =r1( )=2,r2( )=1定义 3.1 给定棋盘 C，令 r0(C)=1,n为 C的格子数，称 R(C)=为 棋盘 C的棋子多项式 。 例如由例 1求得的结果，易知R( )=1+x,R( )=1+2x,R( )=1+2x+x2定理 3.6 给定棋盘 C，指定 C中某格A。令 Ci为 C中删去 A所在行与列所剩的棋盘， Ce为 C中删去格 A所剩的棋盘，则 R(C)=xR(Ci)+R(Ce) (3.11)证明： 将 k个棋子放入棋盘 C，其所有放法可按格 A有棋子与没有棋子分为两类。格 A有棋子相当于在格 A放一个棋子后，再将余下 k-1个棋子放入 Ci，故放法总数为 rk-1(Ci)。格 A没有棋子的放法数为 rk(Ce)。由加法规则rk(C)=rk-1(Ci)+rk(Ce)（此后略）。例 2 计算 R( )与 R( )。 解： R( )=xR( )+R( ）=xR( )+ xR( )+R( )=x(1+2x)+x(1+x)+(1+2x)=1+4x+3x2R( )=xR( )+R( ) =xR( )+ xR( )+R( ) =x(1+2x)+x(1+x)+(1+4x+3x2) =1+6x+6x2
