Jason (jcreed) wrote,

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.
Tags: generating functions, math

  • (no subject)

    Something that's bugged me for a long time is this: How many paths, starting at the origin, taking N steps either up, down, left or right, end up at…

  • (no subject)

    Still sad that SAC seems to end up being as complicated as it is. Surely there's some deeper duality between…

  • (no subject)

    I had already been meaning to dig into JaneSt's "Incremental" library, which bills itself as a practical implementation (in ocaml) of the ideas in…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded