计数原理之递推问题

数学递推关系问题：解决递推关系数学中的递推关系是指一个序列中的每一项都可以由前面一项或多项递推出来的关系。

在解决数学递推关系的问题时，我们通常需要确定递推关系的形式，进而找到规律并求解特定项或整个序列的值。

本文将介绍解决递推关系问题的一般方法和常见技巧。

一、确定递推关系的形式对于给定的数学递推关系，我们首先需要确定它的形式。

递推关系的形式可以通过观察序列中的数值规律来确定。

常见的递推关系形式包括等差数列、等比数列和斐波那契数列等。

以等差数列为例，递推关系通常可表示为：an = an-1 + d，其中an表示第n项，d表示公差。

通过观察序列中相邻项之间的差值是否恒定，我们就可以判断出递推关系的形式。

对于其他形式的递推关系，也可以通过类似的方法进行确定。

需要注意的是，递推关系的形式不一定是唯一的，可能存在多种可能性。

因此，在确定递推关系的形式时，我们需要仔细观察序列中的数值规律，并进行推断和验证。

二、找到规律求解确定递推关系的形式后，我们就可以利用找到的规律来求解特定项或整个序列的值。

以等差数列为例，如果我们已知了序列的首项a1和公差d，可以通过递推公式an = an-1 + d来求解其他项的值。

例如，要求解第n项的值an，可以通过递推公式反复递推计算得到。

除此之外，还可以借助数学方法和工具求解递推关系问题。

例如，对于等比数列，我们可以通过求解特征方程来找到递推关系的通项公式，进而求解特定项的值。

另外，对于一些特殊的递推关系，可能存在已知的求解方法和技巧。

例如，斐波那契数列的递推关系可以通过矩阵乘法或黄金分割公式求解。

三、举例分析为了更好地理解解决递推关系问题的方法和技巧，我们来看一个具体的例子：求解斐波那契数列的第n项的值。

斐波那契数列是一个经典的递推关系，其递推关系可以表示为：Fn = Fn-1 + Fn-2，其中F1 = 1，F2 = 1。

为了求解第n项的值Fn，我们可以使用递推公式反复计算。

递推法解计数问题例析发布时间：2021-06-22T11:22:52.897Z 来源：《中小学教育》2021年第2月6期（下）作者：张淑云[导读] 计数问题是学习和生活中经常遇到的一类问题张淑云湖南省冷水江市铎山镇中心小学 417508摘要：计数问题是学习和生活中经常遇到的一类问题，它的表现形式多样,处理方法灵活,其中递推法是处理复杂计数问题的一种重要方法。

本文通过几个典型例子，说明递推法在解计数问题中的应用。

关键词：计数问题，递推法，例析意大利著名数学家斐波那契（约1170—1250）有一部传世之作《算术之法》，其中提出了一个饶有趣味的问题：假定一对刚出生的兔子一个月就能长成大兔子，再过一个月就开始生下一对小兔子，并且以后每个月都生一对小兔子。

设所生一对兔子为一雌一雄，且均无死亡。

问一对刚出生的小兔一年内可以繁殖成多少对兔子？对于斐波那契提出的这个“兔子繁殖问题”，我们不妨一个月一个月向后推算：开始时有一对小兔，即a0=1；第1个月，这对小兔长成一对大兔，即a1=1；第2个月，这对大兔产下一对小兔，此时共有两对兔子，即a2=2；第3个月，原来的大兔产下一对小兔，第2个月出生的一对小兔长成大兔，即a3=3；第4个月，原来的和第2个月出生的兔子各产下一对小兔，而第3个月出生的一对小兔长成大兔，此时共有5对兔子，即a4=5；…… 如果按照上述“连锁反应”式地繁殖小兔，来推算出一年（12个月）内可以繁殖成多少对兔子，我们确实要费一番功夫。

因此，我们需要找出一个简捷的“连锁反应关系式”来解出a12。

设第n个月共有an对兔子，则an是由两部分构成的，其中一部分是第（n-1）个月的兔子对数an-1；第二部分是由an-2对兔子所生的小兔，共有an-2对。

所以an=an-1+ an-2。

由于a0=1，a1=1，因此每个月的兔子对数依次为：1，1，2，3，5，8，13，21，34，55，89，144，233，…。

华杯赛计数专题: 归纳与递推基础知识:1.递推的基本思想: 从简单情况出发寻找规律, 逐步找到复杂问题的解法。

2.基本类型: 上楼梯问题、直线分平面问题、传球法、圆周连线问题。

3.递推分析的常用思路: 直接累加、增量分析、从复杂化归简单。

例题：例1.一个楼梯共有10级台阶, 规定每步可以迈一级台阶或二级台阶.走完这10级台阶, 一共可以有多少种不同的走法？【答案】89种【解答】设n级台阶有an种走法, 则an=an-1+an-21级有1种走法；2级有（1+1和2）2种走法；3级有（1+1+1、2+1和1+2）3种走法；4级有3+2=5种走法；5级有3+5=8种走法；6级有5+8=13种走法；7级有8+13=21种走法；8级有13+21=34种走法；9级有21+34=55种走法；10级有34+55=89种走法例2.小悦买了10块巧克力, 她每天最少吃一块, 最多吃3块, 直到吃完, 共有多少种吃法？【答案】274种【解答】通过枚举法和递推法: 设n块糖有an种走法, 则an=an-1+an-2+ an-31块糖有1种吃法；2块糖有2种吃法； 3块糖有4种吃法； 4块糖有1+2+4=7种吃法； 5块糖有2+4+7=13种吃法； 6块糖有4+7+13=24种吃法； 7块糖有7+13+24=44种吃法； 8块糖有13+24+44=81种吃法；9块糖有24+44+81=149种吃法；10块糖有44+81+149=274种吃法。

例3.用 1×2的小方格覆盖 2×7的长方形, 共有多少种不同的覆盖方法？【答案】21种【解答】2×1的方格有1种盖法；2×2的方格有2种盖法；2×3的方格有2+1=3种盖法；2×4的方格有3+2=5种盖法；2×5的方格有3+5=8种盖法；2×6的方格有5+8=13种盖法；2×7的方格有8+13=21种盖法。

排列组合经典问题学案1递推关系问题一、阶梯问题例1．问题提出：有阶梯有n级台阶，上台阶时每步只能跨一阶或两阶台阶，问共有多少种走法？（公式：F n=_______________________________________________）注：此公式不需记忆，不需推导，只供增长知识面.10级台阶，上台阶时每步只能跨一阶或两阶台阶，问共有多少种走法？8级台阶，上台阶时每步可以跨一阶、两阶或三阶台阶，问共有多少种走法？10级台阶，要求7步走完，每步可跨一阶，也可跨两阶，问有多少种不同的跨法？10级台阶，上楼可以一步上一级，也可以一步上两级，若从底楼到二楼用8步走完，则不同的走法的种数为？二、圈状染色问题：例2．问题提出：用m种不同的颜色去染如图n个扇形，相邻的扇形之间不能同色，问有多少种不同的涂法？（公式：Q n=_______________________________________________）注：此公式不需记忆，不需推导，只供增长知识面.6种颜色给如下图形涂色，要求相邻区域不能涂同一种颜色，(1) (2) (3)5种颜色给四棱锥、五棱锥的顶点涂色，同一条棱的两个顶点不能同色，问各有多少种不同的涂法？三、传球问题：例3．问题提出：k个人相互传球，已知由甲开始发球，第n次传球后，依然传到甲的不同传球方式共有多少种？次由拿球者再传给其他三人中的任何一人，这样共传6次球，球恰好回到甲手中的传球情形有几种？四、全错位排列问题：例4．问题提出：有n的同学，每人写了1张贺卡，再将这些贺卡混在一起，每人抽取一张，试问每个人拿到的贺卡都不是自己的情形有多少种？(全错位排列公式：___________________________________________)需背记，无需推导]1，2，3，4，5的5个人分别去坐在编号为1，2，3，4，5的座位上，至多有两个号码一致的坐法有__________种排列组合经典问题学案2重点题型问题一、被3整除问题例1．在集合{1,2,3,4,5,6,7,8,9,10}中任选2个数，其和能被3整除的选法共有多少种？{0,1,2,3,4,5,6,7,8,9}中任选3个数，其和能被3整除的选法共有______种{1,3,5,7,9,11,13,15}中任选2个数，其和能被3整除的选法共有____种二、关灯问题：例2．马路上有编号为1、2、3、…、9的9只路灯，为节约用电，现要求把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，也不能关掉两端的路灯，则满足条件的关灯方法共有_____种11只路灯，为节约用电，现要求把其中四只关掉，但不能同时关掉相邻的两只或三只或四只，也不能关掉两端的路灯，则满足条件的关灯方法有____种.三、等价转化的问题例3．射线l1与l2有公共端点O，除端点O外，直线l1上还有A1，A2，A3，A4四个点，在直线l2上还有B1，B2，B3，B4，B5五个点.若在A1，A2，A3，A4四个点中任取一点与B1，B2，B3，B4，B5五个点中各取一点连成一条线段，则这些线段的交点个数最多有多少个？n个点，这n个点两两之间形成一条线段，问这些线段的交点最多有多少个？四、比赛问题例4．某次足球比赛共12支球队参加，分三个阶段进行.(1)小组赛：经抽签分成甲、乙两组，每组6队进行单循环比赛，以积分及净胜球数取前两名；(2)半决赛：甲组第一名与乙组第二名，乙组第一名与甲组第二名作主客场交叉淘汰赛(每两队主客场各赛一场)决出胜者；(3)决赛：两个胜队参加决赛一场，决出胜负.问：全程赛程共需比赛多少场？某年全国足球甲级(A组)联赛共有14队参加，每队都要与其余各队在主客场分别比赛一次，则共进行比赛的场次为__________7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，……直到有一方队员全被淘汰为止，另一方获胜，形成一种比赛过程，那么所有可能出现的比赛过程共有多少种？100名选手之间进行淘汰赛(即一场比赛失败要退出比赛)，最后产生一名冠军，问要举行多少场比赛？五、圆排列问题例5．6个人围成一圈，一共有多少种坐法？6颗不同颜色的钻石，可以穿成几种石圈？排列组合经典问题学案3球盒模型问题按以下要求分配6本不同的书，各有几种方法：1．平均分配甲、乙、丙三人，每人2本；2．平均分成三份，每份2本；3．甲乙丙三人一人得1本，一人得2本，一人得3本；4．分成三份，一份1本，一份2本，一份3本；5．甲乙丙三人中，一人得4本，另外两个每人得1本；6．分成三份，一份4本，加两份每份1本；7．甲得1本，乙得1本，丙得4本；8．分成三份，每份至少1本；9．分给甲乙丙三个人，每人至少1本。

递推关系解计数问题巧用排列计数问题是组合数学中主要而又基本的问题，一般的排列计数问题采用映射、分类、分步、捆绑、插空等方法即可解决，但有些问题（特别是数学竞赛中涉及到的问题）用构建递推关系的方法会更为简洁.本文将通过几个经典问题，讲解用递推方法求排列计数问题的基本策略在一些排列组合问题中，我们可以从简单问题入手，寻找规律，从而可以把问题规律化，找出特征。

领悟它们的奥秘。

比如涉及到排列组合中的上楼梯问题、图形染色问题、传球问题、图形计数问题等。

这些都是与递推有关的计数问题，解答它们的关键是先从简单情形入手，待问题解决后再研究复杂抽象的问题，从中得出一般的规律。

例1，有一楼梯共10级，若规定每次只能跨上一级或二级，要走上10级，问共有多少中走法？分析：设走上n级楼梯的走法有an种，容易知道，a1=1，a2=2，a3=3，a4=5.当n>2时，跨上n级可分为两类：第一步上一级楼梯共有an-1种走法；第二步上二级楼梯有an-2种走法，故共有an=an-1+an-2种走法。

于是a5=8，a6=31，a7=21，a8=34，a9=55，a10=89，还可以一直继续下去，将楼梯变为11级12级13级…等等。

这是著名的斐波拉契数列，其通项公式为an=例2，小华有10块巧克力，每天吃1～3块，吃完为止，问有多少不同的吃法？分析：设n块巧克力有an种吃法，易知a1=1，a2=2，a3=4，a4=7，由此推想，n>3时，an=an-1+an-2+an-3，事实上，当n>3时，n块巧克力的吃法可分三类：第一天吃1块有an-1种吃法；第一天吃2块有an-2种吃法；第一天吃3块后an-3种吃法，故an=an-1+an-2+an-3.当n>3时，a5=13，a6=24，a7=44，a8=81，a9=149，a10=274.因此共有274种吃法。

例3，如图1将一个四棱锥的每一个顶点染上一种颜色，且同一棱上的两端点异色。

计数中的递推关系作者：周文国来源：《中学课程辅导高考版·学生版》2012年第02期利用递推关系求解计数问题是处理排列组合问题的一种有效方法，可从简单的情形着手，逐步递推到一般的情形.现在举例说明如何挖掘和利用计数中的递推关系：一、一阶递推式之整点个数问题例1在直角坐标系中，定义横纵坐标都为整数的点为“整点”，则集合M={(x,y)||x|+|y|≤n,n∈N*}所表示的区域中有多少个整点？分析：可从n分析到n+1进行解决．解：如图，设正方形G n所确定的整点个数为f(n)，则容易知道f(1)=5，当n增加到n+1时，在第一象限就增加了n个整点，由对称性：f(n+1)=f(n)+4n+4，累加知道f(n)=2n2+2n+1，故在n=5时所确定的整点的个数共有f(5)=61个．点评：从f(n)到f(n+1)来分析点的个数的变化．二、一阶递推式之涂色问题例2把一个圆分成n个扇形（n≥2），依次记为D1、D2、……、D n－1、D n，每个扇形都可以用三种不同颜色中的任何一种涂色，要求相邻的扇形颜色不同，若n=4，则共有种不同涂色方法．分析：设涂色方法共有f(n)种，当n=2时，f(2)=6，下面寻求f(n)的递推关系即可．解：D1有3种涂色方法，D2有2种涂色方法，……，D n－1有2种涂色方法，D n仍然有2种涂色方法（不论是否与D1同色），这样共有3×2n－1种涂色方法，这3×2n－1种涂色方法可分为两类：（1）D n与D1同色，虽然与要求不符合，但可以认为D n与D1合为一个扇形，此时涂色方法有f(n－1)种；（2）D n与D1不同色，此时涂色方法有f(n)种．于是3×2n－1=f(n)+f(n－1)，利用数列求和可得到：f(n)=2n+2·(－1)n(n≥2)．则当n=4时，f(4)=18，共有18种不同涂色方法．点评：利用递推式可找出D1、D2、…、D n－1、D n之间的关系，从而确定不同的涂色方法．三、二阶递推式例3一楼梯共有12级，每步可以向上跨1级或2级，共有种上楼梯的方法．分析：设跨到n级楼梯共有f(n)种走法，由题意，跨到n级楼梯需要从n－2级跨到，或从n－1级跨到，前者有f(n－2)种走法，后者有f(n－1)种走法．解：由分类计数原理可以知道f(n)=f(n－1)+f(n－2)，则容易知道f(1)=1，f(2)=2，f(3)=3， f(4)=5，…，故共有f(12)=f(11)+f(10)=233种上楼梯的方法．点评：从解答中可以看到若求f(12)，则必须知道f(11)和f(10)才能解答．四、双元递推式例4用1，2，3这3个数字来构造四位数，但不允许相邻的1出现在四位数中，则这样的四位数共有个．分析：设用1，2，3这3个数字来构造n位数：末位数字为1的有f(n)个，末位数字不为1的有g(n)个，则所有满足条件的n位数共有f(n)+g(n)个，再分这两种情况分析．解：考虑由1，2，3构成的n+1位数：（1）末位数字为1，此类数可由满足要求的n位数中末位不为1的数末位添上1而得到的，故此类数有g(n)个；（2）末位数字不为1，此类数可由满足要求的n位数中末位添上2或3而得到的，故此类数有2［f(n)+g(n)］个．于是f(n+1)=g(n)g(n+1)=2［f(n)+g(n)］，由f(1)=1g(1)=2 ，得到n=4时，f(4)+g(4)=60．点评：通过f(n+1)和g(n+1)双元递推，则问题比较容易解决．（作者：周文国，江苏张家港职业教育中心)。

数学中的递推与迭代小学生了解递推与迭代的原理在数学中，递推和迭代是两种常见的数学方法，用于解决问题和生成数列。

对于小学生来说，了解递推和迭代的原理可以帮助他们更好地理解数学概念，并培养他们的逻辑思维和问题解决能力。

一、递推的原理递推是一种根据前一项或前几项推导后一项的方法。

简单来说，就是通过已知条件计算未知结果。

递推通常使用递推公式或递推关系来表示，常见的递推关系有等差数列和等比数列。

1. 等差数列等差数列是一种数列，其中每一项与前一项之间的差值都相等。

例如，1，3，5，7，9就是一个等差数列，公差为2。

计算等差数列的递推关系很简单，只需要根据前一项和公差相加即可得到后一项。

2. 等比数列等比数列是一种数列，其中每一项与前一项之间的比值都相等。

例如，1，2，4，8，16就是一个等比数列，公比为2。

计算等比数列的递推关系也很简单，只需要根据前一项和公比相乘即可得到后一项。

递推在数学中有着广泛的应用，例如计算斐波那契数列、求解递推方程等。

通过递推，我们能够得到数列中任意一项的值。

二、迭代的原理迭代是一种通过不断重复计算来逼近目标值的方法。

迭代通常使用迭代公式或迭代关系来表示，每次迭代都将上一次的结果作为新的输入，循环进行计算，直到达到某个条件为止。

1. 二分法迭代二分法是一种常见的迭代方法，通过将一个区间不断二分，逼近目标值。

例如，在查找一个数的平方根时，可以利用二分法迭代来逼近。

每次迭代，我们将当前区间的中点作为新的猜测值，然后根据猜测值的平方与目标值的比较结果，将区间缩小一半，逐渐靠近目标值。

2. 牛顿迭代法牛顿迭代法是一种用于求解方程根的迭代方法。

通过不断迭代求导和替换变量的方式，求解方程的近似解。

例如，求解方程f(x)=0的根时，我们可以通过迭代公式x_(n+1) = x_n - f(x_n)/f'(x_n)，不断更新变量x的值，直到满足精度要求。

迭代在数学中也有着广泛的应用，例如求解方程的根、求解最优化问题等。

前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳法、整体法、对应法、递推法．对这些计数方法与技巧要做到灵活运用． 对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法．【例 1】 每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔子来．如果一个人在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔子？【考点】计数之递推法 【难度】3星 【题型】解答【解析】 第一个月，有1对小兔子；第二个月，长成大兔子，所以还是1对；第三个月，大兔子生下一对小兔子，所以共有2对；第四个月，刚生下的小兔子长成大兔子，而原来的大兔子又生下一对小兔子，共有3对；第五个月，两对大兔子生下2对小兔子，共有5对；……这个特点的说明每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，即上上月的兔子数，所以每月的兔子数为上月的兔子数与上上月的兔子数相加． 依次类推可以列出下表：经过月数：---1---2---3---4---5---6---7---8---9---10---11---12兔子对数：---1---1---2---3---5---8--13--21--34--55--89—144，所以十二月份的时候总共有144对兔子．【答案】144【例 2】 树木生长的过程中，新生的枝条往往需要一段“休息”时间供自身生长，而后才能萌发新枝．一棵树苗在一年后长出一条新枝，第二年新枝“休息”，老枝依旧萌发新枝；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则依次“休息”．这在生物学上称为“鲁德维格定律”．那么十年后这棵树上有多少条树枝？【考点】计数之递推法 【难度】3星 【题型】解答【解析】 一株树木各个年份的枝桠数，构成斐波那契数列：1，2，3，5，8，13，21，34，55，89，……所以十年后树上有89条树枝．【答案】89【例 3】一楼梯共10级，规定每步只能跨上一级或两级，要登上第10级，共有多少种不同走法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 登 1级 2级 3级 4级 ...... 10级1种方法 2种 3种 5种 ...... ？ 例题精讲教学目标7-6-4.计数之递推法我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面两个数的和；依此规律我们就可以知道了第10级的种数是89.其实这也是加法的运用：假如我们把这个人开始登楼梯的位置看做A 0，那么登了1级的位置是在A 1，2级在A 2... A 10级就在A 10．到A 3的前一步有两个位置；分别是A 2 和A 1 ．在这里要强调一点，那么A 2 到A 3 既然是一步到了，那么A 2 、A 3之间就是一种选择了；同理A 1 到A 3 也是一种选择了．同时我们假设到n 级的选择数就是An ．那么从A 0 到A 3 就可以分成两类了：第一类：A 0 ---- A 1 ------ A 3 ，那么就可以分成两步．有A 1×1种，也就是A 1 种；(A 1 ------ A 3 是一种选择)第二类：A 0 ---- A 2 ------ A 3， 同样道理 有A 2 ．类类相加原理：A 3 = A 1 ＋A 2，依次类推An = An -1 + An -2．【答案】89【巩固】一楼梯共10级，规定每步只能跨上一级或三级，要登上第10级，共有多少种不同走法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 登 1级 2级 3级 4级 5级 ...... 10级1种方法 1种 2种 3种 4种...... ？我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依此规律我们就可以知道了第10级的种数是28.【答案】28【例 4】 1×2的小长方形(横的竖的都行)覆盖2×10的方格网，共有多少种不同的盖法．【考点】计数之递推法 【难度】4星 【题型】解答【解析】 如果用12⨯的长方形盖2n ⨯的长方形，设种数为n a ,则11a =，22a =,对于3n ≥，左边可能竖放1个12⨯的，也可能横放2个12⨯的，前者有-1n a 种，后者有-2n a 种，所以-1-2n n n a a a =+,所以根据递推，覆盖210⨯的长方形一共有89种．【答案】89【例 5】 用13⨯的小长方形覆盖38⨯的方格网，共有多少种不同的盖法？【考点】计数之递推法 【难度】5星 【题型】解答【解析】 如果用13⨯的长方形盖3n ⨯的长方形，设种数为n a ,则11a =，21a =,32a =,对于4n ≥，左边可能竖放1个13⨯的，也可能横放3个13⨯的，前者有-1n a 种，后者有-3n a 种，所以-1-3n n n a a a =+,依照这31⨯ 32⨯ 33⨯ 34⨯ 35⨯ 36⨯ 37⨯ 38⨯1 1234 6 9 13【答案】13【例 6】 有一堆火柴共12根，如果规定每次取1～3根，那么取完这堆火柴共有多少种不同取法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 取1根火柴有1种方法，取2根火柴有2种方法，取3根火柴有4种取法，以后取任意根火柴的种1根 2根 3根 4根 5根 6根 7根 8根 9根 10根 11根 12根1 2 4 7 13 24 44 81 149 274 504 927【答案】927【巩固】 一堆苹果共有8个，如果规定每次取1～3个，那么取完这堆苹果共有多少种不同取法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 取1个苹果有1种方法，取2个苹果有2种方法，取3个苹果有4种取法，以后取任意个苹果的种【答案】81【例 7】 有10枚棋子，每次拿出2枚或3枚，要想将10枚棋子全部拿完，共有多少种不同的拿法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举．(法1)递推法．假设有n 枚棋子，每次拿出2枚或3枚，将n 枚棋子全部拿完的拿法总数为n a 种．则21a =，31a =，41a =．由于每次拿出2枚或3枚，所以32n n n a a a --=+(5n ≥)．所以，5232a a a =+=；6342a a a =+=；7453a a a =+=；8564a a a =+=；9675a a a =+=；10787a a a =+=．即当有10枚棋子时，共有7种不同的拿法．(法2)分类讨论．由于棋子总数为10枚，是个偶数，而每次拿2枚或3枚，所以其中拿3枚的次数也应该是偶数．由于拿3枚的次数不超过3次，所以只能为0次或2次．若为0次，则相当于2枚拿了5次，此时有1种拿法； 若为2次，则2枚也拿了2次，共拿了4次，所以此时有246C =种拿法． 根据加法原理，共有167+=种不同的拿法．【答案】7【例 8】 如下图，一只蜜蜂从A 处出发，回到家里B 处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？【考点】计数之递推法 【难度】4星 【题型】解答B A A B 1357946821235813213455891 【解析】 蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相邻大号码的蜂房．明确了行走路径的方向，就可以运用标数法进行计算．如右图所示，小蜜蜂从A 出发到B 处共有89种不同的回家方法．【答案】89【巩固】小蜜蜂通过蜂巢房间，规定只能由小号房间进入大号房间问小蜜蜂由A 房间到达B 房间有多少种方法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 斐波那契数列第八项．21种．【答案】21【例 9】 如下图，一只蜜蜂从A 处出发，回到家里B 处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？【考点】计数之递推法 【难度】4星 【题型】解答BA 【解析】 按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算．如右图所示，小蜜蜂从A 出发到B 处共有296种不同的回家方法．【答案】296【例 10】 对一个自然数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到得数为1操作停止．问经过9次操作变为1的数有多少个？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 可以先尝试一下，倒推得出下面的图：2410131112514302831643215167683421其中经1次操作变为1的1个，即2，经2次操作变为1的1个，即4，经3次操作变为1的2个，是一奇一偶，以后发现，每个偶数可以变成两个数，分别是一奇一偶，每个奇数变为一个偶数，于是，经1、2、…次操作变为1的数的个数依次为：1，1，2，3，5，8，…这一串数中有个特点：自第三个开始，每一个等于前两个的和，即即经过9次操作变为1的数有34个.为什么上面的规律是正确的呢？道理也很简单. 设经过n 次操作变为1的数的个数为n a ,则1a =1，2a =1，3a =2，…从上面的图看出，1n a +比n a 大.一方面，每个经过n 次操作变为1的数，乘以2，就得出一个偶数，经过1n +次操作变为1；反过来，每个经过1n +次操作变为1的偶数，除以2，就得出一个经过n 次操作变为1的数. 所以经过n 次操作变为1的数与经过1n +次操作变为1的偶数恰好一样多.前者的个数是n a ,因此后者也是n a 个.另一方面，每个经过n 次操作变为1的偶数，减去1，就得出一个奇数，它经过1n +次操作变为1，反过来.每个经过1n +次操作变为1的奇数，加上1，就得出一个偶数，它经过n 次操作变为1. 所以经过n 次操作变为1的偶数经过1n +次操作变为1的奇数恰好一样多.而由上面所说，前者的个数就是1n a -,因此后者也是1n a -.经过n +1次操作变为1的数，分为偶数、奇数两类，所以11n n n a a a +-=+，即上面所说的规律的确成立.【答案】34【例 11】 有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）【考点】计数之递推法 【难度】5星 【题型】解答【解析】 如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前面3个数相加．现在剩下的不能是质数个，可以看作是质数个的取法总数都是0，然后再进行递推．【答案】25【巩固】有20个相同的棋子，一个人分若干次取，每次可取1个，2个，3个或4个，但要求每次取之后留下的棋子数不是3或4的倍数，有 种不同的方法取完这堆棋子.【考点】计数之递推法 【难度】5星 【题型】填空【解析】 把20、0和20以内不是3或4的倍数的数写成一串，用递推法把所有的方法数写出来：【答案】54【例 12】 4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？【考点】计数之递推法 【难度】5星 【题型】解答【解析】 设第n 次传球后，球又回到甲手中的传球方法有n a 种．可以想象前1n -次传球，如果每一次传球都任选其他三人中的一人进行传球，即每次传球都有3种可能，由乘法原理，共有11333333n n --⨯⨯⨯=()个…(种)传球方法．这些传球方法并不是都符合要求的，它们可以分为两类，一类是第1n -次恰好传到甲手中，这有1n a -种传法，它们不符合要求，因为这样第n 次无法再把球传给甲；另一类是第1n -次传球，球不在甲手中，第n 次持球人再将球传给甲，有n a 种传法．根据加法原理，有11133333n n n n a a ---+=⨯⨯⨯=(个…)．由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以10a =．利用递推关系可以得到：2303a =-=，33336a =⨯-=，4333621a =⨯⨯-=，533332160a =⨯⨯⨯-=．这说明经过5次传球后，球仍回到甲手中的传球方法有60种．本题也可以列表求解．由于第n 次传球后，球不在甲手中的传球方法，第1n +次传球后球就可能回到甲手中，所以只需求出第四次传球后，球不在甲手中的传法共有多少种．从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种．【答案】60【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中．问：共有多少种传球方式？【考点】计数之递推法 【难度】5星 【题型】解答【解析】 递推法．设第n 次传球后球传到甲的手中的方法有n a 种．由于每次传球有4种选择，传n 次有4n 次可能．其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有n a 种，球不在甲的手中的，下一次传球都可以将球传到甲的手中，故有1n a +种．所以14n n n a a ++=．由于10a =，所以12144a a =-=，232412a a =-=，343452a a =-=．即经过4次传球后，球仍回到甲手中的传球方法有52种．【答案】52【例 13】 设A 、E 为正八边形ABCDEFGH 的相对顶点，顶点A 处有一只青蛙，除顶点E 外青蛙可以从正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点E 时青蛙就停止跳动，则青蛙从顶点A 出发恰好跳10次后落到E 的方法总数为 种．【考点】计数之递推法 【难度】5星 【题型】填空【关键词】清华附中【解析】 可以使用递推法．回到A 跳到B 或H 跳到C 或G 跳到D 或F 停在E1步 12步 2 13步 3 14步 6 4 25步 10 46步 20 14 87步 34 148步 68 48 289步 116 48其中，第一列的每一个数都等于它的上一行的第二列的数的2倍，第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和，第四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它的上一行的第四列的数的2倍．这一规律很容易根据青蛙的跳动规则分析得来．所以，青蛙第10步跳到E 有48296⨯=种方法．【答案】96【巩固】在正五边形ABCDE 上，一只青蛙从A 点开始跳动，它每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D 点上就停止跳动．青蛙在6次之内(含6次)跳到D 点有 种不同跳法．【考点】计数之递推法 【难度】5星 【题型】填空AB C DE【解析】 采用递推的方法．列表如下：跳到A 跳到B 跳到C 停在D 跳到E1步 1 12步 2 1 13步 3 1 24步 5 3 25步 8 3 56步 13 8 5其中，根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D 点上就停止跳动．所以，每一步跳到A 的跳法数等于上一步跳到B 和E 的跳法数之和，每一步跳到B 的跳法数等于上一步跳到A 和C 的跳法数之和，每一步跳到C 的跳法数等于上一步跳到B 的跳法数，每一步跳到E 的跳法数等于上一步跳到A 的跳法数，每一步跳到D 的跳法数等于上一步跳到C 或跳到E 的跳法数．观察可知，上面的递推结果与前面的枚举也相吻合，所以青蛙在6次之内(含6次)跳到D 点共有1123512++++=种不同的跳法．【答案】12【例 14】 有6个木箱，编号为1，2，3，……，6，每个箱子有一把钥匙，6把钥匙各不相同，每个箱子放进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把6把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种．【考点】计数之递推法 【难度】5星 【题型】填空【关键词】迎春杯，中年级组，决赛【解析】 (法1)分类讨论．如果1，2号箱中恰好放的就是1，2号箱的钥匙，显然不是“好”的方法，所以“好”的方法有两种情况：⑴1，2号箱的钥匙恰有1把在1，2号箱中，另一箱装的是3～6箱的钥匙．⑵1，2号箱的钥匙都不在1，2号箱中．对于⑴，从1，2号箱的钥匙中选1把，从3～6号箱的钥匙中选1把，共有248⨯=(种)选法，每一种选法放入1，2号箱各有2种放法，共有8216⨯=(种)放法．不妨设1，3号箱的钥匙放入了1，2号箱，此时3号箱不能装2号箱的钥匙，有3种选法，依次类推，可知此时不同的放法有3216⨯⨯=(种)．所以，第⑴种情况有“好”的方法16696⨯=(种)．对于⑵，从3～6号箱的钥匙中选2把放入1，2号箱，有4312⨯=(种)放法．不妨设3，4号箱的钥匙放入了1，2号箱．此时1，2号箱的钥匙不可能都放在3，4号箱中，也就是说3，4号箱中至少有1把5，6号箱的钥匙．如果3，4号箱中有2把5，6号箱的钥匙，也就是说3，4号箱中放的恰好是5，6号箱的钥匙，那么1，2号箱的钥匙放在5，6号箱中，有224⨯=种放法；如果3，4号箱中有1把5，6号箱的钥匙，比如3，4号箱中放的是5，1号箱的钥匙，则只能是5号箱放6号箱的钥匙，6号箱放2号箱的钥匙，有212⨯=种放法；同理，3，4号箱放5，2号箱或6，1号箱或6，2号箱的钥匙，也各有2种放法．所以，第⑵种情况有“好”的放法()1242222144⨯++++=(种)．所以“好”的方法共有96144240+=(种)．(法2)递推法．设第1，2，3，…，6号箱子中所放的钥匙号码依次为1k ，2k ，3k ，…，6k ．当箱子数为n (2n ≥)时，好的放法的总数为n a ．当2n =时，显然22a =(11k =，22k =或12k =，21k =)．当3n =时，显然33k ≠，否则第3个箱子打不开，从而13k =或23k =，如果13k =，则把1号箱子和3号箱子看作一个整体，这样还是锁着1，2两号钥匙，撬开1，2两号箱子，那么方法有2a 种；当23k =也是如此．于是2n =时的每一种情况对应13k =或23k =时的一种情况，这样就有3224a a ==．当4n ≥时，也一定有n k n ≠，否则第n 个箱子打不开，从而1k 、2k 、……、1n k -中有一个为n ，不论其中哪一个是n ，由于必须要把该箱子打开才能打开n 号箱子，所以可以将锁着这把钥匙的箱子与第n 号箱子看作1个箱子，于是还是锁着1k 、2k 、……、1n k -这()1n -把钥匙，需要撬开1，2两号箱子，所以每种情况都有1n a -种．所以()11n n a n a -=-．所以，6542554543225!240a a a a ==⨯==⨯⨯⨯=⨯=，即好的方法总数为240种．【答案】240【巩固】有10个木箱，编号为1，2，3，……，10，每个箱子有一把钥匙，10把钥匙各不相同，每个箱子放进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把10把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种．【考点】计数之递推法 【难度】5星 【题型】填空【解析】 递推法．设第1，2，3，…，6号箱子中所放的钥匙号码依次为1k ，2k ，3k ，…，6k ．当箱子数为n (2n ≥)时，好的放法的总数为n a ．当2n =时，显然22a =(11k =，22k =或12k =，21k =)．当3n =时，显然33k ≠，否则第3个箱子打不开，从而13k =或23k =，如果13k =，则把1号箱子和3号箱子看作一个整体，这样还是锁着1，2两号钥匙，撬开1，2两号箱子，那么方法有2a 种；当23k =也是如此．于是2n =时的每一种情况对应13k =或23k =时的一种情况，这样就有3224a a ==．当4n ≥时，也一定有n k n ≠，否则第n 个箱子打不开，从而1k 、2k 、……、1n k -中有一个为n ，不论其中哪一个是n ，由于必须要把该箱子打开才能打开n 号箱子，所以可以将锁着这把钥匙的箱子与第n 号箱子看作1个箱子，于是还是锁着1k 、2k 、……、1n k -这()1n -把钥匙，需要撬开1，2两号箱子，所以每种情况都有1n a -种．所以()11n n a n a -=-．所以，109829989876543229!=725760a a a a ==⨯==⨯⨯⨯⨯⨯⨯⨯=⨯，即好的方法总数为725760种．【答案】725760前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳法、整体法、对应法、递推法．对这些计数方法与技巧要做到灵活运用． 对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法．【例 15】 每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔子来．如果一个人在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔子？【考点】计数之递推法 【难度】3星 【题型】解答【解析】 第一个月，有1对小兔子；第二个月，长成大兔子，所以还是1对；第三个月，大兔子生下一对小兔子，所以共有2对；第四个月，刚生下的小兔子长成大兔子，而原来的大兔子又生下一对小兔子，共有3对；第五个月，两对大兔子生下2对小兔子，共有5对；……这个特点的说明每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，即上上月的兔子数，所以每月的兔子数为上月的兔子数与上上月的兔子数相加． 依次类推可以列出下表：经过月数：---1---2---3---4---5---6---7---8---9---10---11---12兔子对数：---1---1---2---3---5---8--13--21--34--55--89—144，所以十二月份的时候总共有144对兔子．【答案】144【例 16】 树木生长的过程中，新生的枝条往往需要一段“休息”时间供自身生长，而后才能萌发新枝．一棵树苗在一年后长出一条新枝，第二年新枝“休息”，老枝依旧萌发新枝；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则依次“休息”．这在生物学上称为“鲁德维格定律”．那么十年后这棵树上有多少条树枝？【考点】计数之递推法 【难度】3星 【题型】解答【解析】 一株树木各个年份的枝桠数，构成斐波那契数列：1，2，3，5，8，13，21，34，55，89，……所以十年后树上有89条树枝．【答案】89【例 17】 一楼梯共10级，规定每步只能跨上一级或两级，要登上第10级，共有多少种不同走法？【考点】计数之递推法 【难度】4星 【题型】解答例题精讲教学目标7-6-4.计数之递推法【解析】 登 1级 2级 3级 4级 ...... 10级1种方法 2种 3种 5种 ...... ？我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面两个数的和；依此规律我们就可以知道了第10级的种数是89.其实这也是加法的运用：假如我们把这个人开始登楼梯的位置看做A 0，那么登了1级的位置是在A 1，2级在A 2... A 10级就在A 10．到A 3的前一步有两个位置；分别是A 2 和A 1 ．在这里要强调一点，那么A 2 到A 3 既然是一步到了，那么A 2 、A 3之间就是一种选择了；同理A 1 到A 3 也是一种选择了．同时我们假设到n 级的选择数就是An ．那么从A 0 到A 3 就可以分成两类了：第一类：A 0 ---- A 1 ------ A 3 ，那么就可以分成两步．有A 1×1种，也就是A 1 种；(A 1 ------ A 3 是一种选择)第二类：A 0 ---- A 2 ------ A 3， 同样道理 有A 2 ．类类相加原理：A 3 = A 1 ＋A 2，依次类推An = An -1 + An -2．【答案】89【巩固】一楼梯共10级，规定每步只能跨上一级或三级，要登上第10级，共有多少种不同走法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 登 1级 2级 3级 4级 5级 ...... 10级1种方法 1种 2种 3种 4种...... ？我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依此规律我们就可以知道了第10级的种数是28.【答案】28【例 18】 1×2的小长方形(横的竖的都行)覆盖2×10的方格网，共有多少种不同的盖法．【考点】计数之递推法 【难度】4星 【题型】解答【解析】 如果用12⨯的长方形盖2n ⨯的长方形，设种数为n a ,则11a =，22a =,对于3n ≥，左边可能竖放1个12⨯的，也可能横放2个12⨯的，前者有-1n a 种，后者有-2n a 种，所以-1-2n n n a a a =+,所以根据递推，覆盖210⨯的长方形一共有89种．【答案】89【例 19】 用13⨯的小长方形覆盖38⨯的方格网，共有多少种不同的盖法？【考点】计数之递推法 【难度】5星 【题型】解答【解析】 如果用13⨯的长方形盖3n ⨯的长方形，设种数为n a ,则11a =，21a =,32a =,对于4n ≥，左边可能竖放1个13⨯的，也可能横放3个13⨯的，前者有-1n a 种，后者有-3n a 种，所以-1-3n n n a a a =+,依照这【答案】13【例 20】 有一堆火柴共12根，如果规定每次取1～3根，那么取完这堆火柴共有多少种不同取法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 取1根火柴有1种方法，取2根火柴有2种方法，取3根火柴有4种取法，以后取任意根火柴的种【答案】927【巩固】 一堆苹果共有8个，如果规定每次取1～3个，那么取完这堆苹果共有多少种不同取法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 取1个苹果有1种方法，取2个苹果有2种方法，取3个苹果有4种取法，以后取任意个苹果的种【答案】81【例 21】 有10枚棋子，每次拿出2枚或3枚，要想将10枚棋子全部拿完，共有多少种不同的拿法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举．(法1)递推法．假设有n 枚棋子，每次拿出2枚或3枚，将n 枚棋子全部拿完的拿法总数为n a 种．则21a =，31a =，41a =．由于每次拿出2枚或3枚，所以32n n n a a a --=+(5n ≥)．所以，5232a a a =+=；6342a a a =+=；7453a a a =+=；8564a a a =+=；9675a a a =+=；10787a a a =+=．即当有10枚棋子时，共有7种不同的拿法．(法2)分类讨论．由于棋子总数为10枚，是个偶数，而每次拿2枚或3枚，所以其中拿3枚的次数也应该是偶数．由于拿3枚的次数不超过3次，所以只能为0次或2次．若为0次，则相当于2枚拿了5次，此时有1种拿法；若为2次，则2枚也拿了2次，共拿了4次，所以此时有246C =种拿法． 根据加法原理，共有167+=种不同的拿法．【答案】7【例 22】 如下图，一只蜜蜂从A 处出发，回到家里B 处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？【考点】计数之递推法 【难度】4星 【题型】解答B A A B 1357946821235813213455891 【解析】 蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相邻大号码的蜂房．明确了行走路径的方向，就可以运用标数法进行计算．如右图所示，小蜜蜂从A 出发到B 处共有89种不同的回家方法．【答案】89【巩固】小蜜蜂通过蜂巢房间，规定只能由小号房间进入大号房间问小蜜蜂由A 房间到达B 房间有多少种方法？【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 斐波那契数列第八项．21种．86427531【答案】21【例 23】 如下图，一只蜜蜂从A 处出发，回到家里B 处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？【考点】计数之递推法 【难度】4星 【题型】解答BA【解析】 按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算．如右图所示，小蜜蜂从A 出发到B 处共有296种不同的回家方法．【答案】296【例 24】 对一个自然数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到得数为1操作停止．问经过9次操作变为1的数有多少个？【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 可以先尝试一下，倒推得出下面的图：2410131112514302831643215167683421其中经1次操作变为1的1个，即2， 经2次操作变为1的1个，即4，经3次操作变为1的2个，是一奇一偶，以后发现，每个偶数可以变成两个数，分别是一奇一偶，每个奇数变为一个偶数，于是，经1、2、…次操作变为1的数的个数依次为：1，1，2，3，5，8，…这一串数中有个特点：自第三个开始，每一个等于前两个的和，即即经过9次操作变为1的数有34个.为什么上面的规律是正确的呢？道理也很简单. 设经过n 次操作变为1的数的个数为a ,则a =1，a =1，a =2，…。

递推计数与对应计数一.对应计数法:要计算一个有限集A 的元素个数,若直接计算比较困难时,我们可设法寻找一个便于计算其元素个数的集合B ,并且建立一个A 到B 上的一一对应f ,于是由A B =得到A 的元素个数,这种计数方法就是对应计数方法.运用这种方法的关键是寻找一个便于计算其元素个数的集合B 及如何在A 与B 建立一一对应.例1 圆周上有()4m m ≥个点,每两点连一条弦,如果没有三条弦交于一点(端点除外),问,这些弦在圆内一共有多少个交点?解:圆周上任四点之间所连的弦中在圆内恰有一个交点,反之,圆内的任何一个交点,是由两条弦相交而得,这两条弦对应于圆周上四个点.这样交点与圆周上的四点组之间构成了一个一一对应关系,所以共有4m C 个交点.例2 正方体的12条棱,12条面对角线及4条体对角线,这28条线中,异面直线有几对?解:从正方体的8个顶点中取四个不共面的顶点组成一个四面体,在该四面体的棱所在直线中有3对异面直线;反之,每一对异面线段的四个顶点对应于正方体的4个不共面的顶点.从正方体的8个顶点中取四个不共面的顶点有486658C --=种方法,所以异面直线的对数为358174⨯=.例3 从m n ⨯的棋盘中,取出一个由三个方格组成的L 形,有多少种不同的取法? 解:棋盘中的每一个内部点A 都对应于四个L 形,反之每一个L 形都对应于一个内部点A .m n ⨯的棋盘共有()()11m n --个内部点,所以不同的取法有()()411m n --种.例4 从19,,3,2,1 中,按从小到大的顺序选取4321,,,a a a a 四个数,使得21322,3a a a a -≥-≥,434≥-a a .问符合上述要求的不同取法有多少种?解:等价于去掉六个数,从1,2,3,,13中,按从小到大的顺序选取1234,,,b b b b 四个数共有多少种取法,有413715C =种方法.在此基础上取11223344,1,3,6a b a b a b a b ==+=+=+即可.例5 从集合{}1,2,3,,49中取出6个不同的数,使得其中至少有两个相邻,不同的取法有几种?解:从集合{}1,2,3,,49中取出6个不同的数123456,,,,,a a a a a a 有649C 种不同取法. 若这些数互不相邻,则12345611234544a a a a a a ≤<-<-<-<-<-≤,即等价于从A44个数中选6个不同的数,它们从小到大依次为123456,,,,,b b b b b b ,然后令()11,2,,6i i a b i i =+-=,这样得到的6个数123456,,,,,a a a a a a 即满足条件,反之亦然.所以不同的取法有664944C C -种.例6 圆周上有n 个点(6)n ≥,每两个点连一线段,假设任三条线段在圆内不共点,于是三条两两相交的线段构成一个三角形,试求这些三角形的个数?解:设三角形的顶点有i 个在圆内,3i -个在圆周上,这类三角形的全体为(0,1,2,3)i I i =. 则30nI C =. 对1I ∆∈,有一内点O 为∆的顶点,内点O 为二条线段的交点,对应圆上四点1234,,,A A A A ,13A A 与24A A 交于点O .即内点全体与圆周上四点组全体之间构成一个一一对应,而每个内点O ,又有四个1I 中的∆与之对应,故414n I C =.对2I ∆∈,圆周上任取n 点中的5点,对应2I 中5个∆;反之对每一个2I ∆∈,延长∆的边与圆周交于5个点,使此∆为5点对应的5个∆之一,故525n I C =.对3I ∆∈,则∆三内点确定三条线段交圆周6个点,反之也对,故63n I C =.综上,所以三角形总数为:345645n n n nC C C C +++. 评析:一一映射与倍数映射是转化抽象的,复杂的计数问题的常用方法,但恰当的构造映射是解决问题的关键.二.递推计数法:通过引入数列,建立递推关系来计数的方法称为递推计数法.运用递推方法计数的一般步骤是:(1)求初始值;(2)建立递推关系;(3)利用递推关系求解.例7 由0,1,2,3组成的长度为n 的数字串中,求没有两个0相邻的数字串的个数. 解:设所求数字串的个数为n a ,则长度为n 的数字串可以分为两类:(1)数字串中第一位不为0,则第一位为1,2,3之一,而剩下的长度为1n -的数字串中无两个0相邻的个数为1n a -,由分步计数原理,共有13n a -个;(2) 数字串中第一位为0,则第二位为1,2,3之一,而剩下的长度为2n -的数字串中无两个0相邻的个数为2n a -,由分步计数原理,共有23n a -个;因此我们得到递推关系式()12333n n n a a a n --=+≥,它的特征方程为233x x =+,特征根为32x ±=, 结合初始值124,15a a ==,易得213213422422nnn a ++--=+⎝⎭⎝⎭.例8 4个人互相传球,接球后即传给别人,首先由甲发球,并把它当作第一次传球.求经过n 次传球后,球又回到甲手中的传球方法数.解:设传球方法数为n a ,则120,3a a ==.由甲开始传球1n -次,总传球数为13n -,若经过n 次传球后,球又回到甲手中,则倒数第二次球在另外三个人手中,共有113n n a ---种传法,由此我们得到递推关系式()1132n n n a a n ---=≥,变形为1111134334n n nn a a --⎛⎫-=-- ⎪⎝⎭, 所以()133111134434nn n n n n a a -+⋅-⎛⎫-=--⇒=⎪⎝⎭.例9 有人要上楼,此人每步能向上走1阶或2阶,如果一层楼有18阶,他上一层楼有多少种不同的走法?解(一):此人上楼最多走18步,最少走9步.这里用1817169,,,,a a a a 分别表示此人上楼走18步,17步,16步,…,9步时走法(对于任意前后两者的步数,因后者少走2步1阶,而多走1步2阶,计后者少走1步)的计数结果.考虑步子中的每步2阶情形,易得0118181717C ,C a a ==, 29161699C ,,C a a ==.综上,他上一层楼共有01291817169C C C C 11712014181++++=++++=种不同的走法.解(二):设n F 表示上n 阶的走法的计数结果.显然,121,2F F ==.对于34,,F F 起步只有两种不同走法:上1阶或上2阶.因此对于3F ,第1步上1阶的情形,还剩312-=阶,计2F 种不同的走法；对于第1步上2阶的情形,还剩321-=阶,计1F 种不同的走法.总计321213F F F =+=+=.一般地,对于n F ,第一步走1阶,剩下的1n -阶有1n F -种不同的走法;第一步走2阶,剩下的2n -步有2n F -种不同的走法.所以得到递推关系12n n n F F F --=+. 依次递推得到:432543181716325,538,,258415974181F F F F F F F F F =+=+==+=+==+=+=.例10 求n 位十进制数中出现偶数个6的数的个数.解:设n a 为n 位十进制数中出现偶数个6的数的个数,n b 为n 位十进制数中出现奇数个6的数的个数.则有111199n n n n n n a a b b b a ----=+⎧⎨=+⎩,且118,9a b ==. 从而12212991880n n n n n n a a b a a a -----=++=-,利用特征根法,∴117981022n n n a --=⋅+⋅.。