《高中数学研究性学习案例》容斥原理与高考中的一类排列组合问题王跃进《中学数学研究》2005年第4期文《对一类放球问题的探究》中，对于将“数字填入方格”等放球问题作出推广和证明，是一个成功地运用归纳、猜想、论证的数学思想方法解决问题的范例．本文用组合数学中容斥原理的理论和方法，给出了该问题的一般化的、基本的计数公式，由此计数公式很容易地得到了该问题的递推式及概率等结论，同时也揭示了基本计数公式与这些结论之间的关系．定义将编号为1,2,…,的n个球放入编号为1,2,…,n的n个盒子内，每个盒内放一个球，如果编号为k（1kn）的球恰好放入与其编号不一致（一致）的盒内，我们就称该球错位（相合）。显然，球的错位问题等价于自然数的排列的错位问题。从这些结果可以使我们更全面、更深入地了解中学数学有关问题的一般情形及其理论背景．定理1将编号为1,2,…,n的n个球放入编号为1,2,…,n的n个盒子内，每个盒内放一个球，则n个球均错位的放球方法种数为=（（*）证明设为将编号为1，2，3，…，n的n个球任意放入编号为1,2,…,n的n个盒子内（每个盒内放一个球）的所有放球方法构成的集合，则，又设为编号为k的球相合的所有放球方法构成的集合(只关心编号为k的球，而不考虑其它球是否相合)，，则用心爱心专心，；，；…，，，…，…=1，且，根据容斥原理得=＝=n!－[－+…+(－1)+…+(－1)]=n!－．=．()或写成=．()推论将编号为1,2,…,n的n个球放入编号为1,2,…,n的n个盒子内，每个盒内放一个球，则1）恰好有ｒ个球错位的放球方法种数（记为）为==（1）2）恰好有m个球相合的放球方法种数（记为）为用心爱心专心==（2）证明1）从n个球中选取r球，有种方法；对于取定的r球，使这r个球错位、其余n－r个球相合的放球方法，由定理，有=种；故由乘法原理得=×，化简即得（1）式．2）因为恰好有个球相合等价于恰有个球错位，即=，故在（1）式中令r=n－m即得（2）式．例1同室四个人每人写一张贺年卡，将这四张卡片收回再分发给这四人，每人一张，则每人都分不到自已写的贺年卡的分卡方法共有种．（1993年全国高考题）解问题为定理中n=4的情形，由定理可得所求方法共有种．例2（1991年全国高考·上海卷）设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投入这五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，则这样的投球方法的种数为（A）20；（B）30；（C）60；（D）120解法一从5个球中取出2个球，将它们分别投入与其编号相同的盒内，有种方法；再将其余的3个球分别投入其余的3个盒内，使3个球的编号与盒子的编号不一致，有2种方法。由乘法原理即得所求的投球方法种数为2=20，故选（A）20。解法二问题为推论2）中n=5，m=2的情形，故由（2）式得所求投球方法的种数为=20．例3将标号为1,2,…,10的10个球放入标号为1,2,…,10的10个盒子内，每个盒内放一个球，则恰好有3个球的标号与其所在盒子的标号不一致的放入方法共有种．(以数字作答)（2004年全国高考·湖北卷）（答案240．）解法一从10个球中任取7个球，将它们分别放入与其标号一致用心爱心专心的盒内，有=种方法；再将其余的3个球分别放入其余的3个盒子内，使3个球的标号与其所在盒子的标号不一致，有2种放入方法，由乘法原理即得所求放球方法共有×2=240种．解法二问题为推论中1）的n=10，r=3的情形，故得所求放球方法的种数为=240．用心爱心专心
