组合数学 4.3有禁位的排列

4.3有禁位排列与车多项式,4.3.1有禁位排列4.3.2车多项式4.3.3不相交子棋盘4.3.4相交子棋盘4.3.5举例,4.3.1有禁位排列,有禁位n元排列,12345,a1a2a3a4a5,禁区,棋盘,4.3.1有禁位排列,有禁位n元排列n个棋子布局,12345,a1a2a3a4a5,a2a1a5a4a3,4.3.1有禁位排列,定理4.3.1设B为有禁位n元排列问题的棋盘，rk(B)(k0,1,2,n)(规定r0(B)1)是从棋盘B的不同行不同列取k个禁区的不同方法的数目，则这个有禁位n元排列的个数为N(B)r0(B)n!r1(B)(n1)!r2(B)(n2)!(1)nrn(B)0!,4.3.1有禁位排列,证明n个元素的全排列集合记作E，显然En！令AixxE,且x使第i个元素排在禁区(i1,2,n)n个元素做全排列，先让k个元素排在禁区有rk(B)种方案，而剩下的nk个元素作无限制排列，有(nk)！种方案，即rk(B)(nk)！(1i1i2ikn),4.3.1有禁位排列,于是r0(B)n!r1(B)(n1)!r2(B)(n2)!(1)nrn(B)0!,4.3.2车多项式,定义4.3.1设B为有禁位n元排列问题的棋盘，rk(B)(k0,1,2,n)(规定r0(B)1)是从B的不同行不同列取k个禁区的方案数目，则称多项式R(x,B)r0(B)r1(B)xr2(B)x2r3(B)x3rn(B)xn为棋盘B的车多项式。,4.3.3不相交子棋盘,有禁位5元排列棋盘B,12345,a1a2a3a4a5,15234,a1a5a4a2a3,4.3.3不相交子棋盘,定义4.3.2若棋盘B可分为两个小棋盘B1和B2，且B1中每个禁区与B2中每个禁区都不在同一行同一列，这样的两个子棋盘B1和B2称为不相交的。,4.3.3不相交子棋盘,引理4.3.1设有禁位n元排列问题的棋盘B被分成两个不相交子棋盘B1与B2，则rk(B)r0(B1)rk(B2)r1(B1)rk-1(B2)rk(B1)r0(B2)(k0,1,2,n)证明从棋盘B不同行不同列取k个禁区可分步如下：先从棋盘B1不同行不同列取t(t0,1,2,k)个禁区，有rt(B1)种取法；再从棋盘B2不同行不同列取kt个禁区，有rk-t(B2)种取法。,4.3.3不相交子棋盘,定理4.3.2设有禁位n元排列问题的棋盘B被分成两个不相交的子棋盘B1与B2,则R(x,B)R(x,B1)R(x,B2)推论4.3.1设有禁位n元排列问题的棋盘B被分成m个两两互不相交子棋盘B1,B2,Bm，则R(x,B)R(x,B1)R(x,B2)R(x,Bm),4.3.4相交子棋盘,有禁位5元排列棋盘B,12345,a1a2a3a4a5,15234,a1a5a4a2a3,4.3.4相交子棋盘,12345,a1a2a3a4a5,15234,a1a5a4a2a3,4.3.4相交子棋盘,定理4.3.3子棋盘与如前所述，则(1)rk(B)rk()rk()(2)R(x,B)R(x,)xR(x,)证明从棋盘B不同行不同列取k个禁区分两种：这k个禁区不含S，此时从子棋盘不同行不同列取k个禁区，有rk()种取法；这k个小阴影方块含S，则从子棋盘不同行不同列取k1个禁区，有rk()种取法,4.3.5举例,例4.3.1棋盘B,123456,a1a2a3a4a5a6,152346,a1a5a3a2a4a6,4.3.5举例,123456,a1a2a3a4a5a6,152346,a1a5a3a2a4a6,4.3.5举例,r1(B1)4，r2(B1)2，r3(B1)r4(B1)0R(x,B1)14x2x2r1(B2)2，r2(B2)0R(x,B2)12xr1(B3)1R(x,B3)1xR(x,)(14x2x2)(12x)(1x)17x16x214x34x4,4.3.5举例,r1(B4)4，r2(B4)2，r3(B4)r4(B4)0R(x,B4)14x2x2r1(B5)1R(x,B5)1xr1(B6)3，r2(B6)1，r3(B6)0R(x,B6)13xx2r1(B7)1R(x,B7)1xR(x,)(14x2x2)(1x)(13xx2)(1x)19x30 x247x337x414x52x6,4.3.5举例,R(x,B)R(x,)xR(x,)110 x37x263x354x418x52x6N(B)6!105!374!633!542!181!20!116,4.3.5举例,例4.3.2做集合1,2,n的全排列，但元素1不排在第1位，元素2不排在第2位，元素n不排在第n位，这样的全排列称为集合1,2,n的错排，集合1,2,n的错排的个数简称为集合1,2,n的错排数，记作Dn,4.3.5举例,解错排问题可看作有禁位n元排列问题棋盘B,12n-2n-1