User kakia - MathOverflow

Number of Configurations in the optimal Hanoi tower

2013-04-30T11:54:49Z

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.

computational complexity

2013-01-08T13:13:53Z

I am interested into computational complexity of decision problem: Does a given 2-dimensional simplicial complex contain (any)triangulation of 2-sphere? This problem trivially lies into NP, because certificate is the subset of triangles. I think that it is NP-complete.

Comment by kakia

2013-05-02T13:42:56Z

Well, I see these connections can be arbitrary and there might be no nice way to show the equivalence. I just wanted to have a closed formula for Hanoi tower configurations, from the computational perspective, formulas I see with the equal sequences can be calculated in linear time with respect to $n$, whilst recurrent formula for Hanoi configurations takes cubic time.

Comment by kakia

2013-01-08T22:34:36Z

I agree with connected components and retraction of boundary, but after these operations we are still dealing with quite arbitrary structure. We can even make things "easier" and assume that every edge is incident with at most 3 triangles by simple topological transformation. If we consider dual problem, take 1 vertex in each triangle and connect two vertices if their respective triangles share edges, we get: in somewhat special graph we need to find cubic planar 3-connected subgraph(corresponding to triangulation). Finding cubic subgraph in planar graph is NP-complete. I see some connection.

Comment by kakia

2013-01-08T15:32:41Z

If we are given set of triangles as a certificate, first we will check connectivity, afterwards we check that the link of each vertex is a cycle. If these conditions are satisfied, we know for sure that we have a closed surface. Then calculate Euler characteristic, we are dealing with sphere if and only if Euler characteristic is 2. en.wikipedia.org/wiki/… here you can check what are the Euler characteristics of closed surfaces.