组合数学讲义
（四） 例
例3.1.1 （Hanoi塔问题）这是组合学中著名的问题。n个圆盘按从小到大的顺序一次套在柱A上，如图3.1.1所示。规定每次只能从一根柱子上搬动一个圆盘到另一根柱子上，且要求在搬动过程中不允许大盘放在小盘上，而且只有A、B、C三根柱子可供使用。用an表示将n个盘从柱A移到柱C上所需搬动圆盘的最少次数，试建立数列{an}的递推关系。
A B C
图3.1.1 Hanoi塔问题
（解）特例：a1＝1，a2＝3，对于任何n≥3。 一般情形：：
第一步，将套在柱A的上部的n－1个盘按要求移到柱B上，共搬动了an 1次；
第二步，将柱A上的最大一个盘移到柱C上，只要搬动一次；
第三步，再从柱B将n－1个盘按要求移到柱C上，也要用an 1次。
an 2an 1 1,
由加法法则：
(3.1.3)
a1 1