📄 3_5.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§5 棋盘多项式与有限制排列</title><meta name="GENERATOR" content="Microsoft FrontPage 3.0"><link rel="stylesheet" href="../style.css"></head><body><p align="center"><font size="4"><b>§5 棋盘多项式与有限制排列</b></font></p><p><b>1.有限制排列</b></p><p> 错排问题就是一种有限制条件的排列．<br><b>[例]</b> 4个x，3个y，2个z的全排列中，求不出现xxxx、yyy、zz图象的排列数。<br><b>[解]</b> 出现xxxx图象的排列记为A<sub>1</sub><br> 出现yyy图象的排列记为A<sub>2</sub><br> 出现zz图象的排列记为A<sub>3</sub><br> xxxx作为一个单元出现进行排列，考虑到y重复3次,z重复2次，故<br>｜A<sub>1</sub>｜＝6!／(3!2!)=60，｜A<sub>2</sub>｜＝7!／(4!2!)=105，｜A<sub>3</sub>｜＝8!／(4!3!)＝280，<br>｜A<sub>1</sub>∩A<sub>2</sub>｜＝4!/2!=12,｜A<sub>1</sub>∩A<sub>3</sub>｜＝5!/3!=20,｜A<sub>2</sub>∩A<sub>3</sub>｜＝6!/4!=30,<br>｜A<sub>1</sub>∩A<sub>2</sub>∩A<sub>3</sub>｜＝3!=6,<br>4个x，3个y，2个z的全排列中不同的排列数为9／(4!3!2!)＝1260。所以<br>｜<span class="overline">A</span><sub>1</sub>∩<span class="overline">A</span><sub>2</sub>∩<spanclass="overline">A</span><sub>3</sub>｜<br>=1260－｜A<sub>1</sub>｜－｜A<sub>2</sub>｜－｜A<sub>3</sub>｜+｜A<sub>1</sub>∩A<sub>2</sub>｜+ ｜A<sub>1</sub>∩A<sub>3</sub>｜+｜A<sub>2</sub>∩A<sub>3</sub>｜－｜A<sub>1</sub>∩A<sub>2</sub>∩A<sub>3</sub>｜<br>=1260－(60+105+280)+(12+20+30)－6<br>=871。</p><p><b>2.棋盘多项式</b></p><p> n个不同元素的一个全排列可看做n个相同的棋子在n×n的棋盘上的一个布局。布 局满足同一行（列）中有且仅有一个棋子.<br><img src="3_5_1.gif" align="top" width="227" height="208">如左图,对应的排列为:41352<br> 可以把棋盘C推广到任意形状,如:<br><img src="3_5_2.gif" width="286" height="71"><br></p><p> 布子规定称为无对攻规则，棋子相当于象棋中的车。<br>令r<sub>k</sub>（C）表示k个棋子布到棋盘C上的方案数。如：<br><img src="3_5_3.gif" width="234" height="83"><br>为了形象化起见,( )中就是棋盘的形状.<br><b>[定义]</b> <img src="3_5_4.gif" align="top" vspace="-25" width="357"height="45"><br> 规定 r<sub>0</sub>(C)=1，包括C=Ф时。<br>设C<sub>i</sub>是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；C<sub>e</sub>是仅去掉该格子后的棋盘。<br>在上面定义下，显然有<br> r<sub>k</sub>(C)=r<sub>k－1</sub>(C<sub>i</sub>)＋r<sub>k</sub>(C<sub>e</sub>)， </p><p>即对任一指定的格子，要么布子，所得的方案数为 r<sub>k－1</sub>(C<sub>i</sub>)；要么不布子，方案数为 r<sub>k</sub>(C<sub>e</sub>)。<br>设C有n个格子，则 r<sub>1</sub>(C)＝n．r<sub>1</sub>(C)＝r<sub>0</sub>(Ci) + r<sub>1</sub>(Ce)，<br>∵ r<sub>1</sub>(C<sub>e</sub>)＝n－1<br>∴ r<sub>0</sub>(C<sub>i</sub>)＝1．故规定 r0(C)＝1是合理的．<br>从而:<br><img src="3_5_5.gif" width="229" height="185"><br><img src="3_5_6.gif" width="312" height="125"> </p><p>如果C由相互分离的C<sub>1</sub>，C<sub>2</sub>组成，即C<sub>1</sub>的任一格子所在的行和列中都没有C<sub>2</sub>的格子。则有：<br><img src="3_5_7.gif" width="244" height="165"><br>利用（３）和（４），可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。<br><b>[例]</b><br><img src="3_5_8.gif" width="385" height="200"></p><p><b>3.有禁区的排列</b></p><p><b>[例]</b> 设对于排列P=P<sub>1</sub>P<sub>2</sub>P<sub>3</sub>P<sub>4</sub>，规定P<sub>1</sub>≠３，P<sub>2</sub>≠１、４， P<sub>3</sub>≠2、４， P<sub>4</sub>≠2。<br><img src="3_5_9.gif" align="top" width="239" height="198"><br>这样的排列对应于有禁区的布子。如上图, 有阴影的格子表示禁区。<br></p><p><b>[定理] </b>设r<sub>i</sub> 为i 个棋子布入禁区的方案数，i=1,2,3,···,n。有禁区的布子方案数（即禁区内不布子的方案数）为<br><img src="3_5_10.gif" width="246" height="72"><br><b>[证]</b> 设A<sub>i</sub>为第i个棋子布入禁区，其他棋子任意布的方案集，i =1 , 2 , 3, …,n。 则所有棋子都不布入禁区的方案数为<br><img src="3_5_11.gif" width="494" height="197"><br> 由以上的讨论可知,前面的例子的答案为:4!－6(4－1)!＋11(4－2)!－7(4－3)! ＋1(4－４)!＝4<br></p><p><b>[例]</b> １，２，３，４四位工人，A，B，C，D四项任务。条件如下：<br>１不干B；２不干B、C； ３不干C、D；４不干D。<br>问有多少种可行方案？<br><b>[解]</b> 由题意，可得如下棋盘：其中有阴影的格子表示禁区。<br> <img src="3_5_12.gif" width="239" height="198"><br>因为<br><img src="3_5_13.gif" width="385" height="135"><br>所以方案数为:4!－6(4－1)!+10(4－2)!－4(4－3)!+0(4－4)!=4</p><p><b>[例]</b> 三论错排问题.<br>错排问题对应的是n×n的棋盘的主对角线上的格子是禁区的布子问题。即:<br><span class="overline">C</span>= <img src="3_5_14.gif" align="middle"width="113" height="86"><br> <img src="3_5_15.gif"></p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -