I was talking to my housemate Andreas Krause, who is the very model of "kind of fuckin' brilliant" (a favorite phrase of mine lately, which is just a slightly strengthened version of the original "kind of brilliant" I picked up from
spillourguts) about generating functions a few days ago, and he mentioned that he once tried but failed to figure out a way of writing down one for AVL trees. So of course this has been buzzing around in my head as a challenge since then.Assuming I've got correct the recurrence
A11 = 1
Anm = Σi=0..(n-1) (Ai(m-1)A(n-1-i)(m-1) + Ai(m-2)A(n-1-i)(m-1) + Ai(m-1)A(n-1-i)(m-2))
(That is, the number of AVL trees Anm with n vertices of height m is either made from two subtrees of height m-1 or else one subtree of height m-1 and one of m-2)
Then it seems to me that if you define
g(x,y) = Σn=0..&infinΣm=0..&infin Anm xny2m
then the above recurrence is expressed exactly by the equation
g = x(y2 + g2 + 2(g - ygy(x,0)) g(x,y2))
So the thing is that doing y2m instead of ym and still calling the result a generating function is either (a) cheating (because that sequence is not really the sequence of coefficients of a power series, but rather the exponentially-spaced-out version of it) or (b) a clever generalization (for the same reason) or (c) not really much of a generalization at all, but rather me making too big a deal over the "exponentially-spaced-out" aspect of it. I'm not sure which it is.
I guess the thing is that subsequent to the machinery above, g(x,1) really is a perfectly ordinary generating function for the number of AVL trees of arbitrary height. So I'm going to go with believing option (b) for now.
---
Whoops, no, this is all wrong. I wasted most of today trying three or four other approaches, but nothing panned out. Man, this problem is a tough nut to crack after all.