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

A

_{11}= 1

A

_{nm}= Σ

_{i=0..(n-1)}(A

_{i(m-1)}A

_{(n-1-i)(m-1)}+ A

_{i(m-2)}A

_{(n-1-i)(m-1)}+ A

_{i(m-1)}A

_{(n-1-i)(m-2)})

(That is, the number of AVL trees A

_{nm}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}A

_{nm}x

^{n}y

^{2m}

then the above recurrence is expressed exactly by the equation

g = x(y

^{2}+ g

^{2}+ 2(g - yg

_{y}(x,0)) g(x,y

^{2}))

So the thing is that doing y

^{2m}instead of y

^{m}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.