开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
利用递推数列解决计数问题
刘耀忠 广东潮阳实验学校高中部
有些计数问题需要用递推数列解决。
【例5】（教材问题）如图是瑞典数学家科赫在1904年构造的能够描述雪花形状的图案。图形的作法是：从一个正三角形开始，把每条边分成三等份，然后以各边的中间一段为底边分别向外作正三角形，再去掉底边。反复进行这一过程，就得到一条“雪花”状曲线。设原正三角形（图①）的边长为1，把图①、图②、图③、图④中图形的周长依次记为
【例6】（教材问题）九连环是我国广为流传的一种益智游戏道具,它由九个铁丝圆环相连成串,按一定规则移动圆环的次数,决定解开圆环的个数.在某种玩法中,用an表示解下n(n≤9,n∈N*)个圆环所需的最少移动次数,数列{an}满足a1=1,且
【例7】设n∈N*,对1,2,…,n的一个排列i1i2…in,若s<t,有is>it,则称(is,it)是排列i1i2…in的一个逆序,排列i1i2…in的所有逆序的总个数称为其逆序数.例如:对1,2,3的一个排列231,只有两个逆序(2,1),(3,1),则排列231的逆序数为2.记fn(k)为1,2,…,n的所有排列中逆序数为k的全部数列的个数,则f3(2)=＿＿,f4(2)=＿＿＿,fn(2)(n≥5)的表达式为＿＿(用n表示).
【答案】25(n2-n-2)/2
【解析】记τ(abc)为数列abc的逆序数,对1,2,3的所有排列,
有τ(123)=0,τ(132)=1,τ(213)=1,τ(231)=2,τ(312)=2,
τ(321)=3,所以f3(0)=1,f3(1)=f3(2)=2.
对1,2,3,4的排列,利用已有的1,2,3的排列,将数字4添加进
去,要使逆序数为2,4在新排列中的位置只能是最后三个位置.
因此,f4(2)=f3(2)+f3(1)+f3(0)=5.
对一般的n(n≥4)的情形,逆序数为0的数列只有一个:12…n.所以fn(0)=1.
逆序数为1的排列只能是将排列12…n中的任意相邻两个数字调换位置得到的排列,所以fn(1)=n-1.
为计算fn+1(2),当1,2,…,n的排列及其逆序数确定后,将n+1添加进原排列,n+1在新排列中的位置只能是最后三个位置.
因此,fn+1(2)=fn(2)+fn(1)+fn(0)=fn(2)+n.
当n≥5时,
fn(2)=[fn(2)-fn-1(2)]+[fn-1(2)-fn-2(2)]+…+[f5(2)-f4(2)]+f4(2)=(n-1)+(n-2)+…+4+f4(2)=(n2-n-2)/2,
因此,当n≥5时,fn(2)=(n2-n-2)/2.
【例8】（教材问题）如图所示，有三根针和套在一根针上的若干金属片，按下规则，把金属片从一根针全部移到另一根针上。
（1）每次只能移动1个金属片；（2）较大的金属片不能放在较小的金属片上面。
试推测：把n个金属片从1号针移到3号针，最少需要移动多少次？
【例9】（教材问题）任取一个正整数，若是奇数，就将该数乘3再加上1；若是偶数，就将该数除以2。反复进行上述两种运算，经过有限次步骤后，必进入循环圈1-4-2-1。这就是数学史上著名的“冰雹猜想”（又称“角谷猜想”等）。如取正整数m=6，根据上述运算法则得出6-3-10-5-16-8-4-2-1，共需经过8个步骤变成1（简称为8步“雹程”）。
现给出冰雹猜想的递推关系如下：
【例10】（教材问题）在2015年苏州世乒赛期间，某景点用乒乓球堆成若干堆“正三棱锥“形的装饰品，其他=中第1堆只有1层，就一个球，第2，3，4，……堆最底层（第一层）分别按图中所示方式固定摆放，第二层开始，每层的小球自然垒放在下一层之上，乒乓球，记第堆的乒乓球总数为f(n).
（1）求出f(3);
（2）试归纳出f(n+1)与f(n)的关系式，并根据你得到的关系式探求f(n)的表达式。
【作者简介】刘耀忠，湖北黄冈市人，现就职广东潮阳实验学校。在《中学生数理化》《新高考》《中学数学研究》等杂志发表文章30余篇，主编教辅资料两本。