Combinatorics of Topmost Discs of Multi-Peg Tower of Hanoi Problem

Sandi Klavzar1, Uros Milutinovic2, Ciril Petr3
1Department of Mathematics, PEF, Unversity of Maribor Korodka cesta 160, 2000 Maribor, Slovenia
2Department of Mathematics, PEF, University of Maribor Korogka cesta 160, 2000 Maribor, Slovenia
3Institute of Information Sciences PreSernova 17, 2000 Maribor, Slovenia

Abstract

Combinatorial properties of the multi-peg Tower of Hanoi problem on \(n\) discs and \(p\) pegs are studied. Top-maps are introduced as maps which reflect topmost discs of regular states. We study these maps from several points of view. We also count the number of edges
in graphs of the multi-peg Tower of Hanoi problem and in this way obtain some combinatorial identities.