This question comes from this homework assignment from ECS20 at UC Davis.
How many $n$-disk legal configurations are there for the Tower of Hanoi? A "legal configuration" means that no disk is larger than a disk beneath it on the same peg. All $n$ disks have different diameters.
I am able to prove that the minimum number of required moves for $n$-disks is $2^n – 1$, however is that the maximum number of legal configurations for $n$-disks? I have been thinking about this for a while now and can't come to a conclusion. Any help or pointing in the right direction would be appreciated.
Best Answer
Each disk can go on one of three needles, so there are $3^n$ ways to assign disks to needles. Once you have a set of disks assigned to a needle, the order is determined. Now we have to worry about what of these are "the same" configuration. If the needles are labeled, we are done. If consider the needles interchangeable, most configurations have $3!=6$ alternatives, but the three configurations with all the disks on one needle are special, so we have $\frac {3^n-3}6+1=\frac {3^{n-1}+1}2$ configurations.