<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 2" %>
Simple Explicit Formulas for the Frame-Stewart Numbers
Sandi Klavžar and Uroš Milutinović
Department of Mathematics, PEF, University of Maribor, Koroska cesta 160, 2000 Maribor Slovenia
{sandi.klavzar, uros.milutinovic}@uni-mb.si
Annals of Combinatorics 6 (2) p.157-167 June, 2002
AMS Subject Classification: 05A10, 11B83
Several different approaches to the multi-peg Tower of Hanoi problem are equivalent. One of them is Stewart's recursive formula

In the present paper we significantly simplify the explicit calculation of the Frame-Stewart's numbers S(n,p) and give a short proof of the domain theorem that describes the set of all pairs , such that the above minima are achieved at .
Keywords: multi-peg Tower of Hanoi problem, Frame-Stewart numbers, recursion


1. J.-P. Bode and A.M. Hinz, Results and open problems on the Tower of Hanoi, In: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, 1999, Congr. Numer. 139 (1999) 113–122.

2. N. Claus (= E. Lucas), La Tour d’Hanoi, Jeu de calcul, Science et Nature 1 (8) (1884) 127– 128.

3. P. Cull and E.F. Ecklund, On the Towers of Hanoi and generalized Towers of Hanoi problems, Congr. Numer. 35 (1982) 229–238.

4. P. Cull and I. Nelson, Error-correcting codes on the Towers of Hanoi graphs, Discrete Math. 208/209 (1999) 157–175.

5. H.E. Dudeney, The Canterbury Puzzles (and Other Curious Problems), E.P. Dutton, New York, 1908.

6. O. Dunkel, Editorial note concerning advanced problem 3918, Amer. Math. Monthly 48 (1941) 219.

7. J.S. Frame, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941) 216–217.

8. A.M. Hinz, The Tower of Hanoi, Enseign. Math. 35 (1989) 289–321.

9. A.M. Hinz, The Tower of Hanoi, In: Algebras and Combinatorics, Hong Kong, 1997, Springer, Singapore, 1999, pp. 277–289.

10. A.M. Hinz and A. Schief, The average distance on the Sierpinski gasket, Probab. Theory Related Fields 87 (1990) 129–138.

11. S. Klavzar, U. Milutinovic, and C. Petr, On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Appl. Math. 120 (2002) 141–157.

12. A.A.K. Majumdar, The generalized four-peg Tower of Hanoi problem, Optimization 29 (1994) 349–360.

13. A.A.K. Majumdar, Generalized multi-peg Tower of Hanoi problem, J. Austral. Math. Soc. Ser. B 38 (1996) 201–208.

14. G. Pólya and G. Szegö, Problems and Theorems in Analysis II, Theory of Functions, Zeros, Polynomials, Determinants, Number Theory, Geometry, reprint of the 1976 English translation, Classics in Mathematics, Springer-Verlag, Berlin, 1998.

15. B.M. Stewart, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941) 217– 219.

16. M. Szegedy, In how many steps the k peg version of the Towers of Hanoi Game can be solved?, In: STACS 99, Trier, Lecture Notes in Computer Science 1563, Springer, Berlin, 1999, pp. 356–361.