There is a unique strategy how to move $n$ disks from the first rod to the second optimally and it takes $2^n-1$ steps, solution is obtained by simple recursion. I am interested into the following question, how many times during this strategy we have $a$ disks on the first rod, $b$ disks on the second and $c$ disks on the third. We can solve this question using dynamic programming and recursive relation for the optimal strategy, the recurrent formula is the following:

$dp[a][b][c][n]=dp[a-1][c][b][n-1]+dp[c][b-1][a][n-1]$.

If we consider $n=3k$ and $a=b=c=k$, $dp[k][k][k][3k]$ matches the following sequence ($a_k$ is number of ways to arrange $k$ blue, $k$ red and $k$ green balls so that the first one is fixed and no pair of adjacent balls are of the same color, first and last are also considered adjacent):

http://oeis.org/search?q=2%2c8%2c44%2c268%2c1732

on the first 20 numbers, which makes me believe they are the same, though up to now I was unable to prove equivalence of these two sequences. Note that if we take different number of different color balls, the number of arranging them with the same conditions does not match with the number of respective configurations.

this sequence was suggested in the comments, each number $a_k$ is half of the number in our sequence.

Is it just a coincidence or is there any nice way to show the equivalence? Reduction of the original question on any of these two would give a linear time algorithm to find the number of configurations.

3more comments