From Concrete Mathematics, there is a problem that describes a variation of the Towers of Hanoi, where the disks can not move directly from peg $A$ to peg $B$, but must go through a middle peg. Essentially, you demonstrate that the shortest sequence of moves
$S(n) = 3^n - 1$
I understand this, but the next question asks an extension of this - "Show that, in the process of transferring a tower under (these) restrictions, we will actually encounter every properly stacked arrangement of n disks on $3$ pegs".
The answer given uses a combinatorial approach, indicating that there are $3^n$ possible arrangements of $n$ disks on three pegs (each disk could be on each of three pegs), and since the process involves $3^n - 1$ moves, you must encounter each of these arrangements. This is where my question lies - in those $3^n-1$ moves, there are multiple times where you have the same arrangement (for instance, if you are moving $2$ disks, there are $2$ times when the smallest disk is by itself on the middle peg). This seems to indicate to me that saying that you have $3^n-1$ moves does NOT necessarily mean you hit $3^n$ DIFFERENT arrangements.
I think I'm missing something...
If you had exactly the same configuration twice (That is all three pegs identical), you have a loop wich can be left out. This contradicts the minimality of $3^n - 1$ moves.