递推计数与对应计数

一.对应计数法:

要计算一个有限集A的元素个数,若直接计算比较困难时,我们可设法寻找一个便于计算其元素个数的集合B,并且建立一个A到B上的一一对应f,于是由AB得到A的元素个数,这种计数方法就是对应计数方法.运用这种方法的关键是寻找一个便于计算其元素个数的集合B及如何在A与B建立一一对应.

例1 圆周上有mm4个点,每两点连一条弦,如果没有三条弦交于一点(端点除外),问,这些弦在圆内一共有多少个交点?

解:圆周上任四点之间所连的弦中在圆内恰有一个交点,反之,圆内的任何一个交点,是由两条弦相交而得,这两条弦对应于圆周上四个点.这样交点与圆周上的四点组之间构成了一个一一对应关系,所以共有Cm个交点.

例2 正方体的12条棱,12条面对角线及4条体对角线,这2线中,异面直线有几对?

解:从正方体的8个顶点中取四个不共面的顶点组成一个四面体,在该四面体的棱所在直线中有3对异面直线;反之,每一对异面线段的四个顶点对应于正方体的4个不共面的顶点.

4从正方体的8个顶点中取四个不共面的顶点有C86658种方法,所以异面直线的对数

4为358174.

例3 从mn的棋盘中,取出一个由三个方格组成的L形,有多少种不同的取法? 解:棋盘中的每一个内部点A都对应于四个L形,反之每一个L形都对应于一个内部点A.mn的棋盘共有m1n1个内部点,所以不同的取法有

A

4m1n1种.

例4 从1,2,3,,19中,按从小到大的顺序选取a1,a2,a3,a4四个数,使得a2a12,a3a23,

a4a34.问符合上述要求的不同取法有多少种?

解:等价于去掉六个数,从1,2,3,,13中,按从小到大的顺序选取b1,b2,b3,b4四个数共有多少

4种取法,有C13715种方法.在此基础上取a1b1,a2b21,a3b33,a4b46即可.

例5 从集合1,2,3,种?

解:从集合1,2,3,6种不同取法. ,49中取出6个不同的数a1,a2,a3,a4,a5,a6有C49,49中取出6个不同的数,使得其中至少有两个相邻,不同的取法有几

若这些数互不相邻,则1a1a21a32a43a54a6544,即等价于从

44个数中选6个不同的数,它们从小到大依次为b1,b2,b3,b4,b5,b6,然后令

aibii1i1,2,,6,这样得到的6个数a1,a2,a3,a4,a5,a6即满足条件,反之亦然.

66所以不同的取法有C49C44种.

例6 圆周上有n个点(n6),每两个点连一线段,假设任三条线段在圆内不共点,于是三条两两相交的线段构成一个三角形,试求这些三角形的个数?

解:设三角形的顶点有i个在圆内,3i个在圆周上,这类三角形的全体为Ii(i0,1,2,3). 则

3. I0Cn对I1,有一内点O为的顶点,内点O为二条线段的交点,对应圆上四点A1,A2,A3,A4,A1A3与A2A4交于点O.即内点全体与圆周上四点组全体之间构成一个一一对

4应,而每个内点O,又有四个I1中的与之对应,故I14Cn.

对I2,圆周上任取n点中的5点,对应I2中5个;反之对每一个I2,延长的

5边与圆周交于5个点,使此为5点对应的5个之一,故I25Cn.

6对I3,则三内点确定三条线段交圆周6个点,反之也对,故I3Cn.

3456综上,所以三角形总数为:Cn. 4Cn5CnCn评析:一一映射与倍数映射是转化抽象的,复杂的计数问题的常用方法,但恰当的构造映射是解决问题的关键.

二.递推计数法:

通过引入数列,建立递推关系来计数的方法称为递推计数法.运用递推方法计数的一般步骤是:(1)求初始值;(2)建立递推关系;(3)利用递推关系求解.

例7 由0,1,2,3组成的长度为n的数字串中,求没有两个0相邻的数字串的个数. 解:设所求数字串的个数为an,则长度为n的数字串可以分为两类:

(1)数字串中第一位不为0,则第一位为1,2,3之一,而剩下的长度为n1的数字串中无两个0相邻的个数为an1,由分步计数原理,共有3an1个;

(2) 数字串中第一位为0,则第二位为1,2,3之一,而剩下的长度为n2的数字串中无两个0相邻的个数为an2,由分步计数原理,共有3an2个;

因此我们得到递推关系式an3an13an2n3,它的特征方程为x3x3,特征根为

2x321, 2nn2152132121521321结合初始值a14,a215,易得an.

424222

例8 4个人互相传球,接球后即传给别人,首先由甲发球,并把它当作第一次传球.求经过n次传球后,球又回到甲手中的传球方法数.

n1解:设传球方法数为an,则a10,a23.由甲开始传球n1次,总传球数为3,若经过n次

传球后,球又回到甲手中,则倒数第二次球在另外三个人手中,共有3们得到递推关系式3n1n1an1种传法,由此我

an1ann2,变形为

n1nan11an11n1, n34334an111所以n34433n31. an4

例9 有人要上楼,此人每步能向上走1阶或2阶,如果一层楼有18阶,他上一层楼有多少种不同的走法?

解(一):此人上楼最多走18步,最少走9步.这里用a18,a17,a16,,a9分别表示此人上楼走18步,17步,16步,…,9步时走法(对于任意前后两者的步数,因后者少走2步1阶,而多走1步

012阶,计后者少走1步)的计数结果.考虑步子中的每步2阶情形,易得a18C18,a17C17, 2a16C16,,a9C99.

0129C9117120综上,他上一层楼共有C18C17C1614181种不同的走法.

解(二):设Fn表示上n阶的走法的计数结果.

显然,F11,F22.对于F3,F4,起步只有两种不同走法:上1阶或上2阶.

因此对于F3,第1步上1阶的情形,还剩312阶,计F2种不同的走法；对于第1步上2阶的情形,还剩321阶,计F1种不同的走法.总计F3F2F1213.

一般地,对于Fn,第一步走1阶,剩下的n1阶有Fn1种不同的走法;第一步走2阶,剩下的n2步有Fn2种不同的走法.所以得到递推关系FnFn1Fn2. 依次递推得到:

F4F3F2325,F5F4F3538,,F18F17F16258415974181.

例10 求n位十进制数中出现偶数个6的数的个数.

解:设an为n位十进制数中出现偶数个6的数的个数,bn为n位十进制数中出现奇数个6的数的个数.则有

an9an1bn1,且a18,b19. bn9bn1an1从而an9an19bn2an218an180an2,利用特征根法,∴an78n1910n1.

22