递归计数的六种方式

• 作者: 冯跃峰
• 来源期刊: 中等数学
• 学科: 数学
• 年，卷（期）: 2020,（8）
• 所属期刊栏目: 数学活动课程讲座
• 页码范围: 2-11
• 页数: 10页
• 分类号: O141.3
• 语种: 中文

摘要

(本讲适合高中) 计数是组合中的常见问题,而递归计数则是其常用方法. 所谓递归,就是建立“n”的问题与“小于n”的若干同构子问题之间的等量关系.本文举例介绍六种数学竞赛中常用的递归方式. 1增减元递归 在n的情况中减少或增加一个元素,转化为n-1(或n+1)的情况. 一般采用减首项(排在最前的元素或步骤)的方式建立递归:先考虑首项的取值,再将后面若干项捆绑,看作n-1的情况处理.