《递推计数与对应计数》由会员分享，可在线阅读，更多相关《递推计数与对应计数（5页珍藏版）》请在金锄头文库上搜索。
1、递推计数与对应计数一.对应计数法:要计算一个有限集 A 的元素个数,若直接计算比较困难时,我们可设法寻找一个便于计 算其元素个数的集合B，并且建立一个A到B上的一一对应f ,于是由|A| = |B|得到A的元 素个数,这种计数方法就是对应计数方法.运用这种方法的关键是寻找一个便于计算其元素个 数的集合 B 及如何在 A 与 B 建立一一对应.例1圆周上有m (m 4 )个点，每两点连一条弦，如果没有三条弦交于一点(端点除外)，问，这些 弦在圆内一共有多少个交点?解:圆周上任四点之间所连的弦中在圆内恰有一个交点 ,反之,圆内的任何一个交点 ,是由两条 弦相交而得,这两条弦对应于圆周上四个点.这样
2、交点与圆周上的四点组之间构成了一个一一 对应关系,所以共有 C4 个交点.m例 2 正方体的 12 条棱,12 条面对角线及 4 条体对角线,这 28 条线中,异面直线有几对? 解:从正方体的 8 个顶点中取四个不共面的顶点组成一个四面体,在该四面体的棱所在直线中 有 3 对异面直线;反之,每一对异面线段的四个顶点对应于正方体的 4 个不共面的顶点.从正方体的8个顶点中取四个不共面的顶点有C4 -6-6 = 58种方法，所以异面直线的对数 为 3 x 58 = 174.例3从m x n的棋盘中,取出一个由三个方格组成的L形，有多少种不同的取法？ 解:棋盘中的每一个内部点 A 都对应于四个 L
3、形,反之每一个 L 形都对应于一 个内部点 A . m x n 的棋盘共有 (m -1)(n -1) 个内部点 , 所以不同的取法有 4 (m -1)(n -1)种.例 4 从1,2,3, ,19 中,按从小到大的顺序选取 a , a , a , a 四个数,使得 a - a 2, a - a 3,1 2342132a - a 4 .问符合上述要求的不同取法有多少种?解:等价于去掉六个数，从1,2,3,，仔中，按从小到大的顺序选取b ,b ,b ,b四个数共有多少1234种取法，有C4 = 715种方法.在此基础上取a = b ,a = b +1,a = b + 3,a = b + 6即可.1
4、311223344例5从集合1,2,3,49 中取出6个不同的数，使得其中至少有两个相邻，不同的取法有几种？解:从集合1,2,3,49中取出6个不同的数a ,a ,a ,a ,a ,a有C6种不同取法.1 2 3 4 5 649若这些数互不相邻，则1 a a -1 a - 2 a - 3 a - 4 a - 5 6)，每两个点连一线段，假设任三条线段在圆内不共点，于是三条两两相交的线段构成一个三角形，试求这些三角形的个数?解:设三角形的顶点有i个在圆内，3-i个在圆周上,这类三角形的全体为I(i = 0,1,2,3).则i|I = C 3 -0n对Ae I,有一内点O为A的顶点，内点O为二条线
5、段的交点，对应圆上四点A , A , A , A，AA与A A交于点O.即内点全体与圆周上四点组全体之间构成一个对12341324应,而每个内点O，又有四个I】中的A与之对应，故|/| = 4C4.对Ae I，圆周上任取n点中的5点，对应I中5个A ；反之对每一个Ae I，延长A的2 2 2边与圆周交于5个点，使此A为5点对应的5个A之一，故|I | = 5C5.2n对Ae I，则A三内点确定三条线段交圆周6个点，反之也对，故|I | = C 6.3 3 n综上,所以三角形总数为：C3 + 4C4 + 5C5 + C6 .n n n n评析:一一映射与倍数映射是转化抽象的，复杂的计数问题的常用
6、方法，但恰当的构造映射是 解决问题的关键.二.递推计数法:通过引入数列,建立递推关系来计数的方法称为递推计数法.运用递推方法计数的一般步 骤是:(1)求初始值;(2)建立递推关系;(3)利用递推关系求解.例7由0,1,2,3组成的长度为n的数字串中，求没有两个0相邻的数字串的个数.解:设所求数字串的个数为a，则长度为n的数字串可以分为两类：n数字串中第一位不为0,则第一位为1,2,3之一，而剩下的长度为n -1的数字串中无两个0 相邻的个数为a ，由分步计数原理，共有3a个；n -1n-1 数字串中第一位为0,则第二位为1,2,3之一，而剩下的长度为n - 2的数字串中无两个0 相邻的个数为a
7、，由分步计数原理，共有3a个；n -2n-2因此我们得到递推关系式a = 3a+ 3a(n 3)，它的特征方程为x2二3x + 3，特征根为nn -1n -2结合初始值耳=4, a2二15，易得a =n21n21 - 521 ( 3-何 丫例8 4个人互相传球，接球后即传给别人，首先由甲发球，并把它当作第一次传球.求经过n次传 球后,球又回到甲手中的传球方法数.解:设传球方法数为a，则a = 0,a = 3 .由甲开始传球n -1次，总传球数为3n-1，若经过n次n 12传球后，球又回到甲手中，则倒数第二次球在另外三个人手中，共有3n-1 -a 种传法，由此我 n-1们得到递推关系式3n-1
8、- an-1(n 2),变形为3 I 3n-1所以a1n 3n41 (1 An-141 3丿3n + 3 - (-1)n4例 9 有人要上楼,此人每步能向上走1阶或2阶,如果一层楼有18阶,他上一层楼有多少种 不同的走法?解（一）：此人上楼最多走18步,最少走9步.这里用a ,a ,a，,a分别表示此人上楼走18 1817169步，17步，16步，9步时走法（对于任意前后两者的步数，因后者少走2步1阶,而多走1步2阶,计后者少走1步）的计数结果.考虑步子中的每步2阶情形，易得a二C0 a =,18181717a C2,a C9.161699综上，他上一层楼共有C0 + C1 + C2 + C9
9、 = 1 +17 +120 +1 = 4181种不同的走法.1817169解（二）：设Fn表示上n阶的走法的计数结果.显然，f=1,f2=2 对于F3, F4-起步只有两种不同走法:上1阶或上2阶.因此对于F，第1步上1阶的情形，还剩3-1 = 2阶，计F种不同的走法；对于第1步上232阶的情形，还剩3 - 2 = 1阶，计F种不同的走法.总计F3 = F2 +珥=2 +1 = 3.一般地，对于F，第一步走1阶,剩下的n -1阶有F 种不同的走法;第一步走2阶，剩nn -1下的n - 2步有F种不同的走法所以得到递推关系F = F + F .n -2nn-1n -2依次递推得到：F = F + F = 3 + 2 = 5, F = F + F = 5 + 3 = 8,F = F + F = 2584 +1597 = 4181.4 32543181716例10求n位十进制数中出现偶数个6的数的个数.解:设a为n位十进制数中出现偶数个6的数的个数，b为n位十进制数中出现奇数个6的 nn数的个数.则有a = 9a+ b nn-1n-1b = 9b+ ann -1n -1，且 ai= & bi从而a = 9a + 9b + a = 18a - 80 a ，利用特征根法,nn -1n - 2n - 2n -1n - 2=7 8n-1 + 9 10n-1 .
