刘耀忠——​利用递推数列解决计数问题

请点击上方蓝色字体“邹生书数学”，订阅本微信公众号；请点击右上角的“…”，发送给朋友或分享到朋友圈。

---

公众号“邹生书数学”创建于2018年8月28日。    

开号宗旨：为热爱学习和研究的高中数学教师和教研员搭建学习交流平台，提升教学能力，促进专业发展。本公众号致力传播数学文化，发表教研成果，交流教学经验，探讨数学问题，展示解题方法，分享教学资源，为服务高中教学作贡献。

邹生书，男，1962年12月出生，本科学历，理学士学位，中学数学高级教师，黄石市高中数学骨干教师。主要从事高中数学教学、高中数学解题研究和探究性学习等。从2007年8月到2018年8月，在《数学通讯》《数学通报》《数学教学》《中学数学》《中学数学教学》等，二十多种学术期刊上发表解题和探究性学习文章300余篇。

---

公众号“邹生书数学”诚请高中数学教师、教研员和热爱数学的朋友不吝赐稿。来稿请注明真实姓名、工作单位和联系方式，一般只接受word文档格式的电子稿件，文稿请认真审查，防止错漏，确保无误，文责自负。

本公众号对优秀作者和名师一般会附上“作者简介”，以让广大读者更好地了解作者的研究成果和方向，以便进一步学习作者的相关数学思想或解题方法。

投稿邮箱：[e-mail]；

商务联系：13297228197。

利用递推数列解决计数问题

刘耀忠     广东潮阳实验学校高中部

有些计数问题需要用递推数列解决。

【例5】（教材问题）如图是瑞典数学家科赫在1904年构造的能够描述雪花形状的图案。图形的作法是：从一个正三角形开始，把每条边分成三等份，然后以各边的中间一段为底边分别向外作正三角形，再去掉底边。反复进行这一过程，就得到一条“雪花”状曲线。设原正三角形（图①）的边长为1，把图①、图②、图③、图④中图形的周长依次记为

【例6】（教材问题）九连环是我国广为流传的一种益智游戏道具,它由九个铁丝圆环相连成串,按一定规则移动圆环的次数,决定解开圆环的个数.在某种玩法中,用a_n表示解下n(n≤9,n∈N^*)个圆环所需的最少移动次数,数列{a_n}满足a₁=1,且

【例7】设n∈N^*,对1,2,…,n的一个排列i₁i₂…i_n,若s<t,有i_s>i_t,则称(i_s,i_t)是排列i₁i₂…i_n的一个逆序,排列i₁i₂…i_n的所有逆序的总个数称为其逆序数.例如:对1,2,3的一个排列231,只有两个逆序(2,1),(3,1),则排列231的逆序数为2.记f_n(k)为1,2,…,n的所有排列中逆序数为k的全部数列的个数,则f₃(2)=＿＿,f₄(2)=＿＿＿,f_n(2)(n≥5)的表达式为＿＿(用n表示). 

【答案】25(n²-n-2)/2

【解析】记τ(abc)为数列abc的逆序数,对1,2,3的所有排列,

有τ(123)=0,τ(132)=1,τ(213)=1,τ(231)=2,τ(312)=2,

τ(321)=3,所以f₃(0)=1,f₃(1)=f₃(2)=2.

对1,2,3,4的排列,利用已有的1,2,3的排列,将数字4添加进

去,要使逆序数为2,4在新排列中的位置只能是最后三个位置.

因此,f₄(2)=f₃(2)+f₃(1)+f₃(0)=5.

对一般的n(n≥4)的情形,逆序数为0的数列只有一个:12…n.所以f_n(0)=1.

逆序数为1的排列只能是将排列12…n中的任意相邻两个数字调换位置得到的排列,所以f_n(1)=n-1.

为计算f_n+1(2),当1,2,…,n的排列及其逆序数确定后,将n+1添加进原排列,n+1在新排列中的位置只能是最后三个位置.

因此,f_n+1(2)=f_n(2)+f_n(1)+f_n(0)=f_n(2)+n.

当n≥5时,

f_n(2)=[f_n(2)-f_n-1(2)]+[f_n-1(2)-f_n-2(2)]+…+[f₅(2)-f₄(2)]+f₄(2)=(n-1)+(n-2)+…+4+f₄(2)=(n²-n-2)/2,

因此,当n≥5时,f_n(2)=(n²-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余篇，主编教辅资料两本。

刘耀忠老师往期文章链接：

邹生书数学

2021年第4季度

最受读者欢迎的49篇解题文章

公众号邹生书数学

投稿邮箱：[e-mail]；

商务联系：13297228197.