内容发布更新时间 : 2024/12/27 7:08:19星期一 下面是文章的全部内容请认真阅读。
R1( )=1， R1()=R1（R2()=R2（
）=2， ）=0，
R2()=1，
可以证明布棋方案数Rk（C）具有下面的性质：
对于任意的棋盘C和正整数k，如果k大于C中的方格总数，则R（C）=0。 R1（C）等于C中的方格数。
设C1和C2是两个棋盘，如果C1经过旋转或者翻转变成了C2，则Rk(C1)= Rk(C2)。
设Ci是从棋盘C中去掉指定的方格所在的行和列以后剩余的棋盘，Cl是从棋盘C中去掉指定的方格以后剩余的棋盘，则有Rk(C)= Rk-1(Ci)+ Rk(Cl) (k>=1)。
设棋盘C由两个子棋盘C1和C2组成，如果C1和C2的布棋方案是互相独立
k的，则有Rk(C)??Ri?0i(C1)?Rk?i(C2)。
定义1：设C是棋盘，则
? R(C)??Rk?0k(C)xk
叫做棋盘多项式。
显然，在上述定义中当k大于棋盘的格子数时Rk（C）=0，所以R（C）一般只有有限项。例如：R（）=R0（）+R1（）x+ R 2（）X2=1+2X+X2
根据Rk（C）的性质不难得到R（C）的性质。
R（C）=xR(Ci)+R(Cl)，其中Ci和Cl的定义如前所述。 R（C）=R(Ci)×R(Cl) ，其中Ci和Cl的定义如前所述。 利用这两条性质可以计算棋盘多项式。 例11、 计算R（）。 解：
R（）=X*R（）+R（）
=X（1+X）+（1+2X） =1+3X+X2 。
下面我们就可以利用棋盘多项式来解决有禁区的排列问题。首先可以看到X={1，2，3，……，n}的一个排列恰好对应了n个棋子在n?n棋盘上的一种排布。在图8中，我们以棋盘的n行表示X中的元素，列表示位置，则这种放置方案就对应了排列2143。如果在排列中限制元素i不能放在第j个位置，则相应的布棋方案中的棋盘第i行第j列就不能放置棋子。我们把所有这些不许放置棋的方格称作禁区。
定理1 设C是n?n的具有给定禁区的棋盘，这个禁区 图 8
对应集合{1，2，??，n}中的元素在排列中不允许出现的位置。则这种有禁区的排列数是： n!?r1(n?1)!?r2(n?2)!???(?1)rn 其中ri是i个棋子放置到禁区的方案数。 证明：
n 第11页
先不考虑禁区的限制，那么n 个棋子布到n×n棋盘上的方案有n！·n!个，如果对n个棋子分别编号为1，2，?，n，并且认为编号不同的棋子放入同样的方格是不同的放置方案，那么带编号的棋子布到n×n棋盘上的方案数是n!·n!。我们把这些方案构成的集合记作S。
对j=1，2，…，n，令Pj表示第j个棋子落入禁区的性质，并令Aj是S中具图9
1号棋子落入禁区的方案数为R1，当它落入禁区的某一格之后，2，3，?，n号棋子可以任意布置在(n-1) ×(n-1)的棋盘上，由乘法法则得
A1?R1(n?1)!?(n?1)!
同理，对i=2，3，?，n有
Ai?R1(n?1)!?(n?1)!， 对i求和得
n有性质Pj的方案构成的子集，那么所求的排列数就是A1?A2???An。
?i?1Ai?R1(n?1)!?n!
1号和2号两个棋子落入禁区的方案数为2R2，它们落入以后，3，4，?，n
号棋子可以任意布置在（n－2）*（n-2）的棋盘上，所以
Ai?Aj?2R2(n?2)!?(n?2)!，
对所有的1?i?j?n求和得
?n??2??2??R2(n?2)!(n?2)!， ???R2(n?2)!?n!?Ai?Aj1?i?j?n用类似的方法，我们可以求得
?Ai?Aj?Ak?R3(n?3)!?n!，
1?i?j?n??
A1?A2???An?Rn?n!。
n根据容斥原理，带编号的n个棋子都不落入禁区的方案数是
A1?A2???An?n!?n!?R1(N?1)!?n!?R2(n?2)!?n!???(?1)Rn?n!。
需要说明一点，这个定理适用于n?n棋盘的小禁区的布棋问题。如果是
m?n的棋盘或者是禁区很大的布棋问题，那么只能直接用R（C）来求解。 例12、用四种颜色（红、蓝、绿、黄）涂染四台仪器A，B，C，D。规定每台仪器只能用一种颜色并且任意两台仪器都不能相同。如果B不允许用蓝色和红色，C不允许用蓝色和绿色，D不允许用绿色－和黄色，问有多少种染色方案？ 解：
这个问题就是图中的有禁区的布棋问题。禁区的棋盘多项式为
R（）?1?6x?10x2?4x3,
从而得到R1=6，R2=10，R3=4，根据定理，所求的方案数是
N=4！－6*3！+10*2！－4*1！=24－36+20－4=4。
第12页
例13、错位排列问题也可以看作是有禁区的排列问题，其禁区在主对角线上。下面使用定理来求Dn。 解：
禁区的棋盘多项式是
R（
）=R（）* R（）*??R（） ????? ????????n个
（1?x) =
2nx?x???x?????=1???1??2??n?， ??????n?n??n??n?从而得到R1?1，R2???2??，??，Rn???n??，代入定理得
????
n??n?n?Dn?n!?n(n?1)!???2???(n?2)!???(?1)??n???0!
?????n??n?
11?n1??1?????(?1)?1!2!n!???。
总结：
你觉得“数学好玩”吗？只要你有兴趣，数学就会变得迥然不同。你就会感受到数学无尽的魅力，就会具有攻无不克的意志力，就会产生无坚不摧的战斗力。如果你根本就没爱上数学，又怎么可能碰撞出最为绚烂的火花呢？哪怕非常短暂，瞬间即逝。
有很多同学热爱数学，都为能在数学奥林匹克的赛场上一试身手、摘金夺银而默默钻研，苦苦奋斗。我想学习中保持长久的数学兴趣和培养创造性的思维是成功的关键，也是将来可持续发展的保障。而汲取众家之长是创造性思维的源泉，学会独立思考是提高创造性思维能力的良策。
第13页