《数学奥林匹克专题讲座》第11讲 计数

《《数学奥林匹克专题讲座》第11讲 计数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11讲计数的方法与原理　　计数方法与原理是组合数学的主要课题之一，本讲介绍一些计数的基本方法及计数的基本原理。一、枚举法　　一位旅客要从武汉乘火车去北京，他要了解所有可供乘坐的车次共有多少，一个最易行的办法是找一张全国列车运行时刻表，将所有从武汉到北京的车次逐一挑出来，共有多少次车也就数出来了，这种计数方法就是枚举法。所谓枚举法，就是把所要求计数的所有对象一一列举出来，最后计算总数的方法。运用枚举法进行列举时，必须注意无一重复，也无一遗漏。　　例1四个学生每人做了一张贺年片，放在桌子上，然后每人去拿一张，但不能拿自己做的一张。问：一共有多少种不同

2、的方法？　　解：设四个学生分别是A，B，C，D，他们做的贺年片分别是a，b，c，d。　　先考虑A拿B做的贺年片b的情况（如下表），一共有3种方法。　　同样，A拿C或D做的贺年片也有3种方法。　　一共有3＋3＋3=9（种）不同的方法。　　例2甲、乙二人打乒乓球，谁先连胜两局谁赢，若没有人连胜头两局，则谁先胜三局谁赢，打到决出输赢为止。问：一共有多少种可能的情况？　　解：如下图，我们先考虑甲胜第一局的情况：　　图中打√的为胜者，一共有7种可能的情况。同理，乙胜第一局也有7种可能的情况。一共有7＋7=14（种）可能的情况。二、加法原理如果完成一件事情有n

3、类方法，而每一类方法中分别有m1，m2，…，mn种方法，而不论采用这些方法中的任何一种，都能单独地完成这件事情，那么要完成这件事情共有N=m1+m2+…mn种方法。　　这是我们所熟知的加法原理，也是利用分类法计数的依据。　　例3一个自然数，如果它顺着数和倒着数都是一样的，则称这个数为“回文数”。例如1331，7，202都是回文数，而220则不是回文数。问：1到6位的回文数一共有多少个？按从小到大排，第2000个回文数是多少？　　解：一位回文数有：1，2，…，9，共9个；　　二位回文数有：11，22，…，99，共9个；　　三位回文数有：101，111

4、，…，999，共90个；　　四位回文数有：1001，1111，…，9999，共90个；　　五位回文数有：10001，10101，…，99999，共900个；　　六位回文数有：100001，101101，…，999999，共900个。　　到六位数为止，回文数共有　　9＋9＋90＋90＋900＋900=1998（个）。　　第1999个回文数是1000001，第2000个回文数是1001001。　　例4设有长度为1，2，…，9的线段各一条，现在要从这9条线段中选取若干条组成一个正方形，共有多少种不同的取法？这里规定当用2条或多条线段接成一条边时，除端点外

5、，不许重叠。　　解法1：因为　　所以正方形的边长不大于11。　　下面按正方形的边长分类枚举：　　（1）边长为11：9＋2=8+3=7＋4=6＋5，可得1种选法；　　（2）边长为10：9＋1=8＋2=7＋3=6＋4，可得1种选法；　　（3）边长为9：9=8＋1=7＋2=6＋3=5＋4，可得5种选法；　　（4）边长为8：8=7＋1=6＋2=5+3，可得1种选法；　　（5）边长为7：7=6＋1=5＋2=4＋3，可得1种选法；　　（6）边长≤6时，无法选择。　　综上计算，不同的取法共有　　1＋1+5＋1＋1=9（种）。　　解法2：由于这些线段互不等长，故至

6、少要用7条线段才能组成一个正方形。当恰取7条线段组成正方形时，正方形的3条边各用2条线相接，另一条边只用一条线段；当恰用8条线段时，只能每边各用2条线段相接（容易看出，其他情况不可能发生）。因为1+2＋…＋9=45，45不能被4整除，所以用9条线段，不可能组成正方形。由解法一知，拼出的正方形边长至多为11，又易知正方形的边长不可能为1，2，3，4，5，6。有了以上分析就容易计数了。　　（1）取出7条线段，有以下7种：　　7=1+6＝2＋5＝3＋4；　　8＝1+7＝2+6＝3＋5；　　9＝1＋8＝2＋7＝3＋6=4＋5　　（这个式子有5种）；　　（2

7、）取出8条线段，有以下2种：　　1＋9＝2＋8＝3＋7＝4＋6；　　2＋9＝3＋8＝4＋7＝5＋6。　　综上所述，不同的取法共有7＋2=9（种）。三、乘法原理如果完成一件事必须分n个步骤，而每一个步骤分别有m1，m2，…，mn种方法，那么完成这件事共有N＝m1×m2×…×mn种方法。　　这就是乘法原理，它是分步法的依据。乘法原理和加法原理被称为是计数的基本原理。我们应注意它们的区别，也要注意二者的联合使用。　　例5一台晚会上有6个演唱节目和4个舞蹈节目。求：　　（1）当4个舞蹈节目要排在一起时，有多少不同的安排节目的顺序？　　（2）当要求每2个舞蹈

8、节目之间至少安排1个演唱节目时，一共有多少不同的安排节目的顺序？　　解：（1）先将4个舞蹈节目看成1个节目，与6个演唱节目