6
$\begingroup$

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.

http://oeis.org/A197657

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ The explanation seems likely to be found in the connection between the Tower of Hanoi and the Sierpinski triangle (or gasket). See, for example, cut-the-knot.org/triangle/Hanoi.shtml $\endgroup$
    – Barry Cipra
    Commented Apr 30, 2013 at 18:02
  • 1
    $\begingroup$ On further idle thought, let me change that "seems likely to" to a "might." The connection I thought I saw was illusory. But there might be one I didn't see. $\endgroup$
    – Barry Cipra
    Commented Apr 30, 2013 at 18:20
  • $\begingroup$ I don't think the connection with Sierpinski's triangle helps here. The vertices of the Hanoi graph correspond to the $3^n$ legal positions. However, you only encounter $2^n$ positions as you solve it using a shortest solution, and these are just the solutions along one side of the triangle. However the Hanoi graph does answer mathoverflow.net/questions/128897/…. $\endgroup$
    – Douglas Zare
    Commented May 1, 2013 at 0:55
  • $\begingroup$ By the way, another way to state the recurrence is in terms of generating functions. Let $[x^ay^bz^c]f_k(x,y,z)$ be the number of positions along the shortest solution with $a$ in the original position, $b$ in the middle position, and $c$ in the target position. Then $f_{k+1}(x,y,z) = xf_k(x,z,y) +zf_k(y,x,z)$. $\endgroup$
    – Douglas Zare
    Commented May 1, 2013 at 1:20
  • 2
    $\begingroup$ These appear to be twice oeis.org/A197657, which mentions a definition of a meander. These are row sums of oeis.org/A194595, which filters the meanders. oeis.org/wiki/User:Peter_Luschny/Meander $\endgroup$
    – Douglas Zare
    Commented May 1, 2013 at 14:22

0

Reset to default

You must log in to answer this question.