I have found that there are 27 (3^n) legal states in the 3-disk, 3-peg puzzle. I was wondering if there's a way to calculate the number of illegal configurations or the amount of all possible configurations (and then deduct the legal ones).
Thank you!
On
In the general case, with $n$ disks and $k$ posts, there are $$n!\binom{n+k-1}{k-1}$$ possible positions. To see this note that we can create all positions but arranging the disks in a line in one of $n!$ ways, then splitting the row into $k$ groups and placing the disks in each group on the corresponding peg, in the order they lie in the row. There are $\binom{n+k-1}{k-1}$ ways to do this, by stars and bars. Since there are $k^n$ legal positions, the number of illegal positions is $$n!\binom{n+k-1}{k-1}-k^n$$
When $n=k=3$ this gives $33$.
To calculate the total number of states, we consider cases on how many discs there are in one stack.
If there are three discs in one stack, there are five ways to stack them illegally, and three places for the stack to go, leading to $15$ illegal positions.
If there are two discs in one stack and one in another, there are three ways to choose two discs, exactly one order to make them illegal, and then six ways to choose how to place the stack of size one and the stack of size two, leading to $18$ illegal positions.
If there are three stacks of one disc each then the position is legal.
So there are $33$ illegal positions.