01 计数问题+黄世桥录入.docx

《01 计数问题+黄世桥录入.docx》由会员分享，可在线阅读，更多相关《01 计数问题+黄世桥录入.docx（10页珍藏版）》请在第一文库网上搜索。

1、1计数问题计数方法种类繁多，本章旨在介绍一些基本方法.一、枚举计数枚举计数就是把要计数的对象一一列举出来，最后计算总数的方法.枚举计数的过程中，必须注意不重复也不遗漏，力求有序、有规律、逐一地进行.例I把22分成两个质数之和共有几种不同分法？分析设+8=22,其中纵力都是质数.不妨设WA则可能取2、3、5、7和11,对每一个。值，若b也是质数，则得到一种分法.解设质数。、满足WA+b=22,则”可取2、3、5、7和11.当=2时力=20,不为质数；当=3时，b=9,为质数；当=5时，b=V7,为质数；当=7时，b=15,不为质数；当=11时，b=t为质数.故不同分法有3组，即22=3+19=5

2、+17=11+11.例2如图1-1,沿着边或对角线不重复地从A走到。，一共有多少种走法（这里不重复指走过的点和线段都不重复）？解不同走法有：AD,AED,AECD,ABCD,ATBTCTE-D.一共有5种走法.图1一1例3在一个网格纸（每个小方格都是边长为1的小正方形）中找出4个方格，使得任一个选出的方格都可以通过所选方格的公共边到达另外三个方格，则共有多少种不同选法（通过平移和旋转可以重合的图形认为是相同的）？解依题意可以画出不同选法如下：故一共有7种不同选法.例4在中国古代，有五行相克之说.五行即金、木、水、火、土，而相克是金克木、木克土、土克水、水克火、火克金，从五行中找出互不相克的两行

3、，共有几种不同选法？分析我们可以用“金T木”来表示金克木，从而有金木ff水T火T金，于是可以枚举出所有的选法.解可以选择的两行可以是：（金，土），（金，水），（木，水），（木，火），（土，火）.一共五种.在后面的例题中，我们可能会用到两个符号：P：及CKmWm旭、均为自然数），下面介绍这两个符号表示的意思.（1）旷表示从个元素中任取?个元素的排列数.从个不同的元素中取用个不同的元素按照一定次序排成一列，称为从个元素中取加个元素的一个排列，所有这样不同排列的个数即为匕E,且n(n1)(n-w+1)=mn)，(n-m)其中!=(-1)21,并规定0!=1.证明如下：设一个元素为31WiW,而取的W

4、个元素的排列为加,一,仇1,则明可以是任一0,1),故加有种取法；而历取定后,历只能取i1WiW中除去bi后的任一元素,有一1种取法；类似地，加有一2种取法，品有一M+1种取法，故b、,历，瓦的取法有(-1)(一切+1)种取法.(2)M表示从个元素中任取机个元素的组合数.从个不同元素中取?个元素，不论顺序如何并成一-组，称为从个元素中取M个元素的一个组合，所有这样不同组合的个数即为M,且C：上=里=皿)(皿).mmn-ni)1x2xxm证明如下：首先从个元素阂1WiW”中选取的m个元素的排列有年种，而对其中取定的m个元素历I1WiW的排列数有疗=m!,对于这加种不同的排列，它们的机个元素都是相

5、同的，故属于同一个组合，所以从个元素中取机个元素的组合个数有C-种.tn例5求满足下列条件的所有五位数的个数：任意两个数位上的数字之差的绝对值不小2.分析首先应该求出满足条件的五个数字，然后对每一组数字进行排列，即可求出所有满足条件的五位数的个数.解设五位数为4%g%,设b,岳，方3，方4，岳)=。1，。2，43，。4，as且仇。4+2；03+2;3。2+2；。2。1+2,即a5a4+2a3426a+89,故的，包+2,的+4,g+6,41+8为920内不同的5个数，而相应的，由920内5个不同数也可以对应于的，+2,6+4,s+6,0+8.解依题意90+8V42+6V3+4V52,而对于92

6、0中五个数，bb2b3b4=)22种.但第7次掷出正、反面两种，故共有(9+19+22)x2=)100种掷法.综上，共有不同掷法(1+3+100=)104种.例9有3个红球和8个蓝球排成一圈，任意两个红球之间至少有两个蓝球，问共有多少种不同排列方法(只要把圆旋转一下就重合的排法认为是同一种)？分析我们可以将红球和在它逆时针方向相邻的两个蓝球看成一个整体，例如当成一个白球，这样问题就转化为3白球和两个蓝球的不同圆排列方法.解由于任意两个红球之间至少有两个蓝球，故每个红球的逆时针方向相邻的位置至少有两个蓝球，于是，将每个红球和它逆时针方向相邻的两个蓝球看成一个球，如白球，则满足条件的排列与三个白球

7、、两个蓝球的圆排列是一一映射的.而三个白球、两个蓝球的圆排列的不同排列方法有2种(枚举即可|,故所求的不同排列种类为2种.例10袋中装有红、白球各3个，从袋中拿出球，每次拿一个，要求拿出的白球个数不得多于红球,问有多少种不同拿法？分析由于要求拿出的白球个数不多于红球，故第一个球必是红球.若最后一球为红球，则拿出第5个球时白球数大于红球数，故第6个球必为白球.其他4个球可利用枚举法枚举.解依题意知，第1个球必为红球，第6个球必为白球，而其余4个球的不同拿法有：红红白白、红白红白、红白白红、白红红白、白红白红，一共有5种不同拿法.例11求IOO以内仅能分解为两个素数之积的正整数的个数.分析可以对I

8、SIOO进行因数分解，然后找出符合条件的数；也可以用两个素数相乘，将100以内的数挑出来.显然，后一种方法简单一些.解50以内素数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47共15个.设分解素因数后为abt其中a100,不满足要求.综上，满足条件的数有(15+10+6+3=)34个.二、分类思想与加法原理加法原理是指完成一件事情可以分为?类，第1类有m种方法，第2类有2种方法，第?类有,”种方法，完成这件事情的不同方法总数为N=ZZi+？+.例12一位解放军打靶，他打了3枪，共21环，而每枪可以打1一10环，问他有多少种不同的打法(要求考虑打枪的次序)，分

9、析设三枪分别为。、b、C环，则1W,b,CWI0,+%+c=21于是x(,b,c)7.将,b,c重排列为,b,fct且WNWd对.对c=7,8,9,10分类讨论即可得到总的打法数.解设三枪依次为人氏C环，对,b,c重排列为优，6,c,且优bc.若d=7,则此时=y=7,共有1种打法.若d=8,则(/，N)可取(5,8)、(6,7).当(，6)=(5,8)时,有3种打法;当(a,b)=(6,7)时,有(印=)6种打法.即共有9种打法.若d=9,则(储，可取(3,9)、(4,8)、(5,7)、(6,6).当(,b)=(3,9)或(6,6)时，各有3种打法；当(，6)=(4,8)、(5,7)时，各有

10、6种打法.即共有18种打法.若d=IO,则(,日)可取(1,10)、(2,9)、(3,8)、(4,7)、(5,6).当(，力=(1,10)时，有3种打法；当(，力取其他值时，各有6种打法.即共有(3+6x4)=27种打法.综上，由加法原理，一共有(1+9+18+27=)55种不同打法.例13由1、2、3这3个数组成六位数，要求相邻数位上的数字都不相同，有多少个满足条件的六位数？分析依题意知，不可能有一个数字出现在4个数位上，所以可能是两个数字分别出现3次，也可能是三个数字分别出现1、2、3次或者2、2、2次，再用加法原理对上述三种可能下的个数求和即可.解依题意知，不可能有某个数字出现在4个数位上，故每个数字至多出现3次.若为两个数字各出现3次，那么两个数字必间隔排列，即有2个不同的六位数.而这两个数字可以是(1,2)、(1,3)或(2,3),故有(2x3=)6个不同的六位数.若为三个数字且分别出现1、2、3次，首先各个数字出现不同的情况共有(8=)6种，对于其中任一种，不妨设1出现3次，2出现2次，3出现1次，先将两个2与3排成一排(有3科排法)再与3个1间隔