《竞赛数学中的组合数学问题.pdf》由会员分享，可在线阅读，更多相关《竞赛数学中的组合数学问题.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 1 页组合数学论文竞赛数学中的组合数学问题第 2 页竞赛数学中的组合数学问题组合数学是上个世纪五十年代后逐步建立和完善起来的一门数学分支，组合数学也称为组合学、组合论，组合分析。教科书上对组合分析的定义：按某种要求把一些元素构成有限集合的研究叫做组合分析。这种研究比传统的数学讨论的对象更广泛，在实际生活和实践活动中应用性更大。这种研究一般讨论以下问题：在一定的约束条件下，对象构成的存在性（有与没有、能与不能）问题；构成的分类与计数；构成的方法（构造方法）及最优化方法。人们常把竞赛中某些问题称为杂题，又称为组合数学问题。为什么？中学数学竞赛中的一些问题，很难把它们归类为代数问题或几何问题，但
2、它们涉及到的解题目标和解题方法可以归入组合问题和组合分析；当然一些组合数学的习题也直接用作竞赛题。初等数学竞赛中的组合问题与组合分析常用的方法有抽屉原理、递推（归）原理、容斥原理、染色方法等，这些原理方法都很一般，重要的是经验和技巧应用的能力。本文重点研究竞赛数学中的组合数学计数问题。计数问题组合数学中的计数问题，数学竞赛题中的熟面孔，看似司空见惯，不足为奇很多同学认为只要凭借课内知识就可左右逢源，迎刃而解其实具体解题时，时常会使你挖空心思，也无所适从。对于这类问题往往首先要通过构造法描绘出对象的简单数学模型，继而借助在计数问题中常用的一些数学原理方可得出所求对象的总数或其范围。1、计数中求最
3、大值：第一步：分类讨论（1）情况一，推出目标数f m1；（2）情况二，推出目标数f m2；,（s）情况 s，推出目标数f ms；第二步：m0=maxm1，m2，ms，则 f m0；第三步：构造模型使计数恰好等于常数m0，则常数m0即为最大值。另一种叙述:第 1 步：由目标数f m 推出可以符合条件；第 2 步：由 f=m+1 推出是不能符合条件；所以fmax=m。2、计数中求最小值：第一步：分类讨论（1）情况一，推出目标数f m1；（2）情况二，推出目标数f m2；,（s）情况 s，推出目标数f ms；第二步：m0=minm1，m2，ms，则 f m0；第三步：构造模型使计数恰好等于常数m0，
4、则常数m0即为最小值。另一种叙述:第一步：由目标数f m 推出可以；第 3 页第二步：由目标数f=m1 推出不能；所以fmin=m。下面我们从一道简单的组合问题说起：如图，每个正方体的六个面上分别写着数字1，2，3，4，5，6，并且任意两个相对的面上所写的两个数字之和都等于7。把这样的 4 个正方体一个挨着一个连接起来后，紧挨着的两个面上的数字之和都等于8。图中标着 x 的那个面上所写的数字是几？分析：拐角处正方体前后分别为4，3，则右侧面可能是 1 或 6，而 1 不能使 x 面的对面数字为 7，故只能为 6，所以 x 的对面数字为 2，所以，x=5。著名的赛题图 1 证明：任意六个人中，总
5、有三个人，要么相互认识，要么相互不认识。同色分析三步：把实际问题转化为图形染色；抽屉原理；二分法推理。证明：圆上六个点 A1A2A3A4A5A6表示六个人，两人相互认识，相应两点间连红线，两人不相识，相应两点间连蓝线，原命题即为证明存在三边同色的三角形。与A1相连的 5 条线分别染两种颜色，至少有三条线同色。不妨设至少有三条红线，且为A1A2、A1A3、A1A4。若A2、A3、A4三点间的连线有一条红线，则有红色三角形；否则，三条连线都是蓝线，存在蓝色三角形。图 2 例 1、由 9 位裁判给参加健美比赛的12 名运动员评分。每位裁判对他认为的第一名运动员给 1 分，第二名运动员给2 分，,，第
6、12 名运动员给 12 分。最后评分结果显示：每名运动员所得的9 个分数中高低分之差都不大于3 分。设各运动员的得分总和分别为e1，e2，e3，e12，且 e1 e2 e3 e12，求 e1 的最大值。分析：含 1 分的格子最多有 4 列，此 4 列的每格数字平均不超过22.5，3 列呢？2 列？1 列？解：对 9 个 1 分布的列数进行讨论：（1）1 分分布在同一列，该列的和为 9，e1=9；（2）1 分恰在两列中，列中数字不超过4，两列的和最大为 59=45，较小的列和 452，是整数，则较小的列和 22，故最小的列和 e122(21)；（3）1 分恰在三列中，列中数字不超过4，三列的和最
7、大为 89=72，同理e124；（4）1 分恰在四列中，列中数字不超过4，四列的和最大为 109=90，同理e122；图 3（5）1 分恰在 5 列中，5 列 45 个数都只能取 1、2、3、4，9 个裁判只能给出9个 1、2、3、4，共 36 个，填不满 5 列；同理，1 分不能分布在比 5 更多的列中。所以，1 最多能在 4 列中。故e124。第 4 页若前三列中，每列三个1、三个 3、三个 4，每列的和都是 24，第四列 5 个 2，4个 5，和为 30；第五列 4 个 2，5 个 5，和为 33；以后第 k 列填 9 个 k，和为 9k54。则 e1=24。所以 e1 的最大值为 24
8、。例 2、有两副扑克牌，每副牌的排列顺序是：第一张是大王，第二张是小王，然后是黑桃、红桃、方块、梅花4 种花色排列，每种花色的牌又按A，2，3，,，J，Q，K的顺序排列。某人把按上述排列的两副扑克牌上下叠在一起，然后从上到下把第一张丢掉，把第二张放在最底层，把第三张丢掉，把第四张放在最底层,，如此下去，直至最后剩下一张牌。则所剩的这张牌是什么？我们先来看下下面这道题，是一个小学的竞赛题，称为“做数学”。依顺时针方向将数字1，2，3，4，5，6，7 写在圆周上。首先将数字1 删除，然后每次跳过一个未删除的数，删除被跳到位置上的数，依此方法继续进行直到最后只剩下一个数为止。例如，删除数字 1，跳过
9、数字 2；删除数字 3，跳过数字 4；删除数字 5，跳过数字 6；删除数字 7，跳过数字 2；删除数字 4，跳过数字 6；删除数字 2，所以，剩下最后的一个数是6。图 4 如果依顺时针方向将1，2，3，,，2004 写在圆周上，并依照上述规则操作，试问最后剩下的一个数为。解：第一圈:从 1 开始，删去所有奇数，余下2k 型数：2，4，6，8，,，2002，2004；第二圈:从 2 开始，删去所有 4k-2 型数，余下 4k 型数：4，8，12，16，,，2000，2004；第三圈:从 4 开始，删去所有 8k+4 型数，余下 8k 型数：8，16，24，,，1992，2000；第四圈:从 16
10、 开始，删去所有 16k 型数，余下 16k-8 型数：8，24，40，,，1976，1992；第五圈:从 24 开始，删去所有 32k-8 型数，余下 32k-24 型数：8，40，72,，1960，1992；第六圈:从 8 开始，删去所有 64k-56 型数，余下 64k-24 型数：40，104，,，1896，1960；第六圈:从 8 开始，删去所有 64k-56 型数，余 64k-24 型数：40，104，,，1896，1960；第七圈:从 104 起，删去所有 128k-24 型数，余 128k-88 型数：40，168，296，424，552，680，808，936，1064，11
11、92，1320，1448，1576，1704，1832，1960；第八圈:从 40 起，删去所有 256k-216 型数，余 256k-88 型数：168，424，680，936，1192，1448，1704，1960；第九圈:从 168 起,删去所有 512k-344 型数，余 512k-88 型数：424，936，1448，1960；第十圈:删去 424，1448，余下：936，1960；最后，删去 936，余下 1960。第 5 页分析：下面我们回顾刚才那道题，也来“做数学”。解：依次把牌编为 1，2，3，,，108；第一圈:从 1 开始，删去所有奇数，余下2k 型数：2，4，6，8，,
12、，108；第二圈:从 2 开始，删去所有 4k-2 型数，余下 4k 型数：4，8，12，16，,，108；第三圈:从 4 开始，删去所有 8k-4 型数，余下 8k 型数：8，16，24，,，104；第四圈:从 8 开始，删去所有 16k 型型数，余下 16k-8 数：8，24，40，56，72，88，104；第五圈:从 8 开始，删去 8，40，72，104，余下 24，56，88；第六圈:删去 56，余下 24，88；再删 24，最后留 88。88=54+2+13 2+6，第 88 号牌为第二副牌中的方块6。有没有更好的处理方法？我们发现，当牌数为4 张时，最后留下的是4 号牌；当牌数为
13、 8 张时，最后留下的是8 号牌；当牌数为 2k张时，最后留下的是2k号牌；现在共有 108 张牌，取掉 44 张时，恰好余 64 张；按约定先去掉 44 张牌，第 44 张是开始排列中的第87 号牌，而第 88 号牌被放到余下的 64 张牌的最后，故最后留下的是第88号牌。请用此方法计算 1，2，,，2004 余下的最后的数？因为 20041024=980，所以第 980 个被去掉的数是第一轮中的1959(980 21)，第 981 个被去掉的数是 1961，从这儿按规则数最后的数是前面的1960。从 1，2，3，2004中任选 k 个数，使得所选的k 个数中，一定可以找到能构成三角形边长的
14、 3 个数(这里要求三角形三个边长互不相等)。试问：满足条件的k 的最小值。考虑等价命题：1，2，3，,，2004 中存在 k1 个数，其中任意 3 个数均不能构成一个三角形的3 条边长 (这里要求三角形三个边长互不相等)。求满足此条件的 k 的最大值。分析：从小的数开始，找尽量多的数，使之不能构成三角形两小边之和不大于第 3 边：1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，16 个数！再增加数一定会有两小边之和大于第3 边了，所求的 k 的最大值为 17。怎样表达？解：按条件 an-2+an-1 an2004 构造递增的正整数数列 an
15、，并使得 an值最小 n最大：1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，共 16 个数！其中任意 3 个数 ai、aj、ak(ijk)，总有 ai+aj ak-2+ak-1 ak，两小数之和大于第 3 数，不能成为三角形的3 条边。对于任意的、项数不少于17 且每项值不超过2004的、递增的正整数数列bn ，若存在 bi、bj、bk(ijk 17)满足 bi+bjbk，则此 3 个数可以成为三角形的 3 边边长；否则，bk ak(k17)，b15+b16 a15+a162004 b17，b15，b16，b17可以成为三角形的3 边边长。
16、即所求的 k 的最小值为 17。例 3、在 23 的矩形方格纸上，各个小正方形的顶点称为格点。以格点为顶点第 6 页的等腰直角三角形有（）个A24 B38 C46 D50 解：（1）直角边为 1 的三角形有 46=24 个；（2）直角边为 2 的三角形有 42=8 个；（3）直角边为2的三角形有 42+6=14个；图 5（4）直角边为5的三角形有 4 个；1、运用分类计数原理与分步计数原理分类计数原理与分步计数原理（即加法原理与乘法原理）是关于计数的两个基本原理，是解决竞赛中计数问题的基础。下面提出的三个问题，注意结合排列与组合的相关知识，构造出相应的模型再去分析就可顺利求解。例 4、已知两个
17、实数集合12100,Aa aa与1250,Bbbb，若从 A到 B的映射 f 使得 B 中每个元素都有原象，且12100()()()fafafa，则这样的映射共有（）个。（A）50100C、（B）4899C、（C）49100C、（D）4999C解：设1250,b bb按从小到大排列为1250ccc（因集合元素具有互异性，故其中不含相等情形）。将 A中元素121 00,aaa分成 50 组，每组依次与 B中元素1250,ccc对应这里，我们用1231452a a a c a a c，表示1231()()()fafafac=，452()()fafac，,考虑12100()()()fafafa，容易
18、得到10050()fac，这就是说50c只能写在100a的右边，故只需在123989910050aaaaaac之间的 99 个空位“”中选择 49 个位置并按从左到右的顺序依次填上124 9,ccc。从而构成满足题设要求的映射共有4999C个。因此选 D。例 5、有人要上楼，此人每步能向上走1 阶或 2 阶，如果一层楼有18 阶，他上一层楼有多少种不同的走法？解法 1：此人上楼最多走 18 步，最少走 9 步。这里用1817169,aaaa分别表示此人上楼走 18 步，17步，16 步，,，9 步时走法（对于任意前后两者的步数，因后者少走 2 步 1 阶，而多走 1 步 2 阶，计后者少走 1
19、 步）的计数结果。考虑步子中的每步 2 阶情形，易得01818Ca，11717Ca，21616Ca，,，999Ca。综上，他上一层楼共有01291817169CCCC11712014181种不同的走法。解法 2：设nF表示上 n 阶的走法的计数结果。显然，11F，22F（2 步 1 阶；1 步 2 阶）。对于34,FF起步只有两种不同走法：上 1 阶或上 2 阶。第 7 页因此对于3F，第 1 步上 1 阶的情形，还剩312阶，计2F种不同的走法；对于第 1 步上 2 阶的情形，还剩321阶，计1F种不同的走法。总计321213FFF。同理：432325FFF，543538FFF，,，1817
20、16258415974181FFF。例 6、在世界杯足球赛前，F 国教练为了考察127,AAA这七名队员，准备让他们在三场训练比赛（每场90 分钟）都上场。假设在比赛的任何时刻，这些队员中有且仅有一人在场上，并且1234,AAAA每人上场的总时间（以分钟为单位）均被 7 整除，567,AAA每人上场的总时间（以分钟为单位）均被13 整除。如果每场换人次数不限，那么按每名队员上场的总时间计算，共有多少种不同的情况。解：设1,2,7iAi上场的总时间分别为1,2,7iai分钟。根据题意，可设71,2,3,4iiak i，135,6,7iiaki，其中1,2,7ikiZ。令41iikm，75iikn
21、，其中4m，3n，且,m nZ。则713270mn。易得其一个整数特解为333mn，又因7,131，故其整数通解为331337mtnt。再由33134373tt，得29013t，故整数0,1,2t。从而其满足条件的所有整数解为33,20,7,3;10;17.mmmnnn。对于4133iik的正整数解，可以写一横排共计33 个 1，在每相邻两个 1 之间共 32 个空位中任选 3 个填入“+”号，再把 3 个“+”号分隔开的 4 个部分里的 1 分别统计，就可得到其一个正整数解，故4133iik有332C个正整数解1234,kkkk；同理753iik有22C个正整数解567,kkk；从而此时满足
22、条件的正整数解1234567,kkkkkkk有32322CC个。因此满足条件的所有正整数解1234567,kkkkkkk有323232322199616CCCCCC496034884240042244个，即按每名队员上场的总时间计算，共有 42244 种不同的情况。2、运用容斥原理容斥原理，又称包含排斥原理或逐步淘汰原理。顾名思义，即先计算一个较大集合的元素的个数，再把多计算的那一部分去掉。它由英国数学家J.J.西尔维斯特首先创立。这个原理有多种表达形式，其中最基本的形式为：设12,nAAA是任意 n 个有限集合，则12nAAA1121111.niijijkninijnijknAAAAAAAA
23、A 例 7、由数字 1，2，3 组成 n 位数，且在这个 n 位数中，1，2，3 的每一个至少出现一次，问这样的n 位数有多少个？解：第 8 页设 U是由 1，2，3 组成的 n 位数的集合，1A是 U中不含数字 1 的 n 位数的集合，2A是 U中不含数字 2 的 n 位数的集合，3A是 U中不含数字 3 的 n 位数的集合，则3nU；1232nAAA；1223311AAAAAA；1230AAA。因此|31iiA123122331123UAAAAAAAAAAAA33 23 1033 23nnnn。即符合题意的 n 位数的个数为3323nn。下面，我们再来看一个关于容斥原理应用的变异问题。例
24、8、参加大型团体表演的学生共240 名，他们面对教练站成一行，自左至右按1，2，3，4，5，,依次报数。教练要求全体学生牢记各自所报的数，并做下列动作：先让报的数是 3 的倍数的全体同学向后转；接着让报的数是 5 的倍数的全体同学向后转；最后让报的数是7 的倍数的全体同学向后转。问：此时还有多少名同学面对教练？面对教练的同学中，自左至右第66 位同学所报的数是几？解：设1,2,3,240U，iA表示由 U中所有 i 的倍数组成的集合。则240U；3240803A，5240485A，7240347A；152401615A，212401121A，35240635A；1052402105A。从而此时
25、有35715213510524136UAAAAAAA名同学面对教练。如果我们借助维恩图进行分析，利用上面所得数据分别填入图 6，注意按从内到外的顺序填。如图 1，此时面对教练的同学一目了然，应有109+14+4+9=136名。用上面类似的方法可算得自左至右第1 号至第 105 号同学中面对教练的有60 名。考虑所报的数不是3，5，7 的倍数的同学没有转动，他们面对教练；所报的数是3，5，7 中的两个数的倍数的同学经过两次转动，他们仍面对教练；其余同学转动了一次或三次，都背对教练。从 106 开始，考虑是 3、5、7 的倍数：3 的倍数（由 105依次加 3）：108，111，114，117，1
26、20，,5 的倍数（由 105依次加 5）：110，115，120，,7 的倍数（由 105依次加 7）：112，119，,因此，从 106 号开始，自左至右，面对教练的同学所报的数依次是：106，107，109，113，116，118，120，,由此可知面对教练的第66 位同学所报的数是118。三、抽屉原则55 14 9 2 4 28 19 109 图 6 第 9 页10 个苹果放入 9 个抽屉中，无论怎么放，一定有一个抽屉里放了2 个或更多个苹果。这个简单的事实就是抽屉原则。由德国数学家狄利克雷首先提出来的。因此，又称为狄利克雷原则。将苹果换成信、鸽子或鞋，把抽屉换成信筒、鸽笼或鞋盒，这个
27、原则又叫做信筒原则、鸽笼原则或鞋盒原则。抽屉原则是离散数学中的一个重要原则，把它推广到一般情形就得到下面几种形式：原则一：把 m 个元素分成 n 类（m n），不论怎么分，至少有一类中有两个元素。原则二：把 m 个元素分成 n 类（mn）（1）当 n|m 时，至少有一类中含有至少nm个元素；（2）当 n|m 时，至少有一类中含有至少nm+1 个元素。其中 n m 表示 n 是 m 的约数，n m 表示 n 不是 m 的约数，nm 表示不超过nm的最大整数。原则三：把1221nmmm个元素分成 n 类，则存在一个 k，使得第 k 类至少有km个元素。原则四：把无穷多个元素分成有限类，则至少有一类
28、包含无穷多个元素。以上这些命题用反证法极易得到证明，这里从略。一般来说，适合应用抽屉原则解决的数学问题具有如下特征：新给的元素具有任意性。如 10 个苹果放入 9 个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着。问题的结论是存在性命题，题目中常含有“至少有,”、“一定有,”、“不少于,”、“存在,”、“必然有,”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果。对一个具体的可以应用抽屉原则解决的数学问题还应搞清三个问题：（1）什么是“苹果”？（2）什么是“抽屉”？（3）苹果、抽屉各多少？用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内
29、考虑问题，从而使问题变得简单明确。用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律。用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律。用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”。例 9、在 1，4，7，10，13，,，100 中任选出 20 个数，其中至少有不同的两组数，其和都等于 104，试证明之。（第 39 届美国普特南数学竞赛题）证明：给定的数共有 34 个，其相邻两数的差均为3，我们把这些数分成如下18 个不相交的集合：1，52，4，100，7，97，,49，55。且把它们分作是
30、18 个抽屉，从已知的34 个数中任取 20 个数，即把前面两第 10 页个抽屉中的数 1 和 52 都取出，则剩下的18个数在后面的 16 个抽屉中至少有不同的两个抽屉中的数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是 104。评述：此例是根据某两个数的和为104 来构造抽屉。一般地，与整数集有关的存在性问题也可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而构成抽屉。例 10、设 ABC 为一等边三角形，E是三边上点的全体.对于每一个把 E分成两个不相交子集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点？（第24 届 IMO第 4 题）证明
31、：如图 7，在边 BC、CA、AB上分别取三点 P、Q、R，使。3,3,3ABRBCAQABCPC显然 ARQ，BPR，CQP 都是直角三角形.它们的锐角是 30及 60。设 E1，E2是 E的两个非空子集，且2121,EEEEE由抽屉原则 P、Q、R中至少有两点属于同一子集，不妨设P、Q E1。如果 BC边上除 P之外还有属于 E1的点，那么结论已明。设 BC的点除 P之外全属于 E2，那么只要 AB上有异于 B的点 S属于 E2，设 S在 BC上的投影点为，则 SS B为直角三角形。再设 AB内的每一点均不属于E2，即除 B之外全属于 E1，特别，R、AE1，于是 A、Q、RE1，且 AQ
32、R 为一直角三角形。从而命题得证。评述：此例通过分割图形构造抽屉。在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个或几个抽屉进行讨论，使问题得到解决。4、割补法的应用计算几何中的割补法在组合数学中即表现为计数上的“割补”：欲求解一定范围内满足条件的元素个数，不妨扩大限定范围求解，例如减法原理；抑或在统计中分别求解，再将多余部分删去，例如容斥原理。总之，退一步海阔天空，先放宽条件，再解决问题就方便多了。（1）减法原理这只是一个简单的数学问题而已，可以看成是加法原理和乘法原理的一个引申：假设 A地到 B，C，D地
33、分别有 5 条路，但到 E地只有 3 条路，B，C，D，E地与 F 都有 3 条路相通，于是不妨假设 AE也有 5 条路相通，于是 AF 道路总数为 543=60条，其中有 23=6条是我们“杜撰”出来的，于是实际上AF道路总数应为 606=54条。（2）有禁区的排列问题我们先介绍有关棋盘多项式的概念。设 C是一个棋盘，Rk(C)表示把 k 个相同的棋子布到C 中的方案数。在布棋时我们规定：当一个棋子放到C 中的某个格以后，这个格所在的行和列就不能再放其他棋子了，并规定对任意的棋盘C 有 R0(C)=1。不难得到以下的结果：第 11 页R1()=1，R1()=R1（）=2，R2()=R2（）=
34、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的布棋方案是互相独立的，则有kiikCRC021ik)()(R(C)R。定义 1：设 C是
35、棋盘，则0k)(RR(C)kkxC叫做棋盘多项式。显然，在上述定义中当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，
36、n的一个排列恰好对应了 n个棋子在nn棋盘上的一种排布。在图 8 中，我们以棋盘的 n行表示 X 中的元素，列表示位置，则这种放置方案就对应了排列2143。如果在排列中限制元素 i 不能放在第 j 个位置，则相应的布棋方案中的棋盘第i行第 j 列就不能放置棋子。我们把所有这些不许放置棋的方格称作禁区。定理 1 设 C是nn的具有给定禁区的棋盘，这个禁区图 8 对应集合 1，2，,，n中的元素在排列中不允许出现的位置。则这种有禁区的排列数是：nnrnrnrn)1()!2()!1(!21其中ri是 i 个棋子放置到禁区的方案数。证明：第 12 页先不考虑禁区的限制，那么n 个棋子布到 n n 棋盘
37、上的方案有n！n!个，如果对 n个棋子分别编号为1，2，,，n，并且认为编号不同的棋子放入同样的方格是不同的放置方案，那么带编号的棋子布到n n棋盘上的方案数是n!n!。我们把这些方案构成的集合记作S。对 j=1，2，n，令 Pj表示第 j 个棋子落入禁区的性质，并令Aj是 S 中具有性质 Pj的方案构成的子集，那么所求的排列数就是nAAA21。图 9 1 号棋子落入禁区的方案数为R1，当它落入禁区的某一格之后，2，3，,，n 号棋子可以任意布置在(n-1)(n-1)的棋盘上，由乘法法则得)!1()!1(11nnRA同理，对 i=2，3，,，n 有)!1()!1(1nnRAi，对 i 求和得!
38、)!1(11nnRAnii1 号和 2 号两个棋子落入禁区的方案数为2R2，它们落入以后，3，4，,，n号棋子可以任意布置在（n2）*（n-2）的棋盘上，所以)!2()!2(22nnRAAji，对所有的nji1求和得!)!2()!2()!2(22221nnRnnRnAAnjiji，用类似的方法，我们可以求得!)!3(31nnRAAAnjikji，,!21nRAAAnn。根据容斥原理，带编号的n 个棋子都不落入禁区的方案数是!)1(!)!2(!)!1(!2121nRnnRnNRnnAAAnnn。需要说明一点，这个定理适用于nn棋盘的小禁区的布棋问题。如果是nm的棋盘或者是禁区很大的布棋问题，那么
39、只能直接用R（C）来求解。例 12、用四种颜色（红、蓝、绿、黄）涂染四台仪器A，B，C，D。规定每台仪器只能用一种颜色并且任意两台仪器都不能相同。如果B不允许用蓝色和红色，C不允许用蓝色和绿色，D不允许用绿色和黄色，问有多少种染色方案？解：这个问题就是图中的有禁区的布棋问题。禁区的棋盘多项式为R（）3241061xxx,从而得到 R1=6，R2=10，R3=4，根据定理，所求的方案数是N=4！6*3！+10*2！4*1！=2436+204=4。第 13 页例 13、错位排列问题也可以看作是有禁区的排列问题，其禁区在主对角线上。下面使用定理来求Dn。解：禁区的棋盘多项式是R（）=R（）*R（）*
40、,R（）个n=nx)1（=nxnnxnxn2211，从而得到11R，22nR，,，nnRn，代入定理得!0)1()!2(2)!1(!nnnnnnnDnn!1)1(!21!111nn。总结：你觉得“数学好玩”吗？只要你有兴趣，数学就会变得迥然不同。你就会感受到数学无尽的魅力，就会具有攻无不克的意志力，就会产生无坚不摧的战斗力。如果你根本就没爱上数学，又怎么可能碰撞出最为绚烂的火花呢？哪怕非常短暂，瞬间即逝。有很多同学热爱数学，都为能在数学奥林匹克的赛场上一试身手、摘金夺银而默默钻研，苦苦奋斗。我想学习中保持长久的数学兴趣和培养创造性的思维是成功的关键，也是将来可持续发展的保障。而汲取众家之长是创造性思维的源泉，学会独立思考是提高创造性思维能力的良策。