2

I was looking into a recurrence relation related to the Tower of Hanoi and how many times a particular $a,b,c$ appears where $a$ disks are on the left peg, $b$ disks are on the middle peg, and $c$ disks are on the right peg, with the final tower on the right peg for all $n=a+b+c$.

The recurrence relation I found is as follows $$f(a,b,c) = f(a-1,c,b) + f(c-1,a,b)$$ with base case $$f(k,0,0) = f(0,0,k) = 1$$$$f(0,k,0)=0$$$$f(a,b,c)=0,\ \text{any of}\ a,b,c\ \text{negative}$$

I've been reading through Generatingfunctionology by Herbert S. Wilf, but I don't think this kind argument swapping appears in the book.

I've gotten as far as $$F(x,y,z) = \sum f(a,b,c) x^a y^b z^c$$ $$F(x,y,z) = xF(x,z,y) + zF(z,x,y)$$ and hit a brick wall.

Any suggestions welcome.

Sherlock9
  • 245
  • Assuming your work is right, then $F(x,y.z) = 0 / (1-x-z) = 0 $. It's likely you made some mistake, esp with the substitution at the end (Don't you need to drop out the base case?) – Calvin Lin Mar 09 '23 at 21:14
  • @CalvinLin Would that be $F(x,y,z) = x \left(F(x,z,y)-1 \right) + z \left(F(z,x,y) -1 \right)$? – Sherlock9 Mar 10 '23 at 06:46

1 Answers1

1

I have found a plain generation function that doesn't use any argument swapping! Unfortunately, it's a little complex.

What I've found so far is $$f(a,b,c)=f(c,b,a)\ (1)$$ $$f(a,b,c)=f(a-1,c,b)+f(c-1,a,b)\ (2)$$ $$=f(b,c,a-1)+f(b,a,c-1)\ (3)$$ If we expand $(2)$ $$f(a-1,c,b)=f(a-2,b,c)+f(b-1,a-1,c)\ (4)$$ $$f(c-1,a,b)=f(c-2,b,a)+f(b-1,c-1,a)\ (5)$$ Upon expanding the second terms of $(4)$ and $(5)$ $$f(b-1,a-1,c)=f(b-2,c,a-1)+f(c-1,b-1,a-1)$$ $$f(b-1,c-1,a)=f(b-2,a,c-1)+f(a-1,b-1,c-1)$$ Adding these last two relations together, we get $$f(b-1,a-1,c)+f(b-1,c-1,a)=\left[f(b-2,c,a-1)+f(b-2,a,c-1)\right]+2f(a-1,b-1,c-1)$$ Which via $(3)$ is $$=f(a,b-2,c)+2f(a-1,b-1,c-1)$$ After collecting all the terms and using relation $(1)$ $$f(a,b,c)=f(a-2,b,c)+f(a,b-2,c)+f(a,b,c-2)+2f(a-1,b-1,c-1)$$ As for the corresponding generating function, $$F(x,y,z)=x^2F(x,y,z)+y^2F(x,y,z)+z^2F(x,y,z)+2xyzF(x,y,z)-(x+z+x^2+z^2+xy+yz+2xyz)$$ Leaving us with a generating function that I have no idea how to analyze $$F(x,y,z)=\frac{x+z+x^2+z^2+xy+yz+2xyz}{1-x^2-y^2-z^2-2xyz}$$ Edit: Upon further analysis, the correct generating function may be $$F(x,y,z)=\frac{x+z+xy+yz+1-y^2}{1-x^2-y^2-z^2-2xyz}$$ which only differs in that $f(0,0,0)=1$ instead $0$ now. No idea if that helps or harms the analysis.

Sherlock9
  • 245