用容斥原理对相合与更列问题的研究VIP免费

《高中数学研究性学习案例》容斥原理观点下的一类放球问题及其概率王跃进纵观这些年的全国数学高考题，可以看到有些排列组合的题目有着较深的组合数学背景知识，研究这些问题，不能仅限于中学数学的知识与方法技巧，因为仅用中学数学的知识和方法只能解决一些简单的、具体的问题，而看不到问题的一般性情况下的解决方法．我们有必要用组合数学中的某些理论来研究中学数学里的几种排列组合问题，这不仅有助于对题目本身更深入的了解，而且对提高数学素养和应用数学知识去解决问题的能力也是有益的．容斥原理在研究相合与禁位排列中起了重要的作用．《中学数学研究》2005年第4期文《对一类放球问题的探究》中，对于“将数字1,2,3,4填入标号为1,2,3,4的四个方格”和“将编有数字1,2,3,4,5的球放入编号为1,2,3,4,5的五个箱子”这两个问题作出推广、猜想、和证明，给出了这类问题在一般情形下的递推和通项公式．本文给出了该问题的一般化的、本质的计数公式，从而也比较容易地推出了该问题的其它递推和通项公式．我们将“数字填入方格”和“编号的球放入编号的箱子”的问题统一为下面的定义．定义设是自然数的一个排列，如果，即数字排在其自然顺序下的位置，就称此排列有一个数字相合；一个排列若无任何数字相合，称此排列为更列．例如，当n=5时，排列14352中有两个数字1、3相合；排列34152为更列．定理1将自然数1，2，3，…，n进行全排列，记为其中至少有一个数字相合的排列的种数；记为其中为更列的排列的种数，则用心爱心专心=（1）=（2）证明先证（1）式．设为数字1，2，3，…，n的所有全排列构成的集合，则，又设为数字相合的所有排列构成的集合(只考虑数字)，，则，；，；…，，，…，…=1，且，根据容斥原理得=|A1∪A2∪…∪An|=…+(-1)+…+(-1)=－+…+(－1)+…+(－1)=．再证(2)式：因为=+，即n!=+，故=n!－，将(1)式代入右端即得证．推论１=证明由（１）式得==+用心爱心专心=．推论２=n+．证明由（2）式得==+=n+．推论3=+（从n个不同元素中选取k个的排列数,下同）证明==++…）++…）=+推论4=+．证明==++…）++…）=+．例1（93年全国高考题）同室四个人每人写一张贺年卡，将这四张卡片收回再分发给这四人，则每人都分不到自已写的贺年卡的分卡方法共有种．解法一：（中学数学的解法）将四张卡片任意分给这四人，共有4！=24种，需要从中减去用心爱心专心有人分到自已写的卡片的方法数．通过按分到自已写的卡片的人数分类计算，可知四人中恰有１人、２人、３人、４人分到自已写的卡片的方法数分别为、、、种，故四人均分不到自已写的卡片的方法数为．此题考查了用正反相辅的方法解决问题的能力，但是当数字大于4时，仍用上述分类计算的方法则很麻烦，用组合数学中的容斥原理，可知例1只是一般的更列数中的简单情形．例２将五个人写的卡片再分发给这五个人，每人一张，则五人中每人都分不到自已写的卡片的分卡方法共有，而例1为n=4时的更列问题：．注：有人给出更列数=，当时，它是正确的，但当时，，而正确结果为=44．故一般有≠．该问题的进一步拓广是：定理2在1，2，3，…，n共n个数字的全排列中，恰有个数字未排在其自然顺序下原来的位置上的排列种数为=．证明从n个数字中取出r个数字，有种方法；对于取定的r个数字，使这r个数字更列、其余n－r个数字相合的排列，由定理1有=种，由乘法原理即得证．例如，将五封信随便装入五个信封中，则恰有四封信装错的方法共有用心爱心专心种．例3将标号为1,2,…,10的10个球放入标号为1,2,…,10的10个盒子内，每个盒内放一个球，则恰好有3个球的标号与其所在盒子的标号不一致的放入方法共有种．(以数字作答)（04年全国高考·湖北卷）（答案240．）解法一从10个球中取出7个球，有=种方法；对于取定的7个球，将它们分别放入与其标号一致的盒子内只有1种方法，再将其余的10－7=3个球分别放入其余的3个盒子内，且使3个球的标号与其所在盒子的标号不一致的放入方法有2种，由乘法原理即得所求的放球方法有×1×2=240种．解法二问题为定理２中n=10，r=3的情形，故得所求的放球方法种数为=240．例2（1991年全国高考·上海卷）设有编号为1，2，3，4，5...