sniffnoy | Wherein Harry finds a function

It occured to be a bit after PROMYS last year that while we (the Arithmetree group) had found a formula for the size of a+b where a and b are binary trees, we had not done so for the extension to *general* trees in the second half of Loday's paper. I realized that the reason that formula worked was because it was f(rdeg(x),ldeg(y)) where f(a,0)=f(0,a)=1 and f(a,b)=f(a-1,b)+f(a,b-1) (and thus f(a,b)=(a+b) choose a), and that, with the general trees, it would also be f(rdeg(x),ldeg(y)), with f(a,0)=f(0,a)=1, but, because of the middle-plus term, we would instead have f(a,b)=f(a-1,b)+f(a,b-1)+f(a-1,b-1).

Now the question became, can I find an explicit formula for this function?

So I calculated out some small values and I stared at it and I didn't know what to make of it. And I tried bizarre things with the choose function and none of it worked. So I gave up on it.

Now it happened that last week I was thinking about Arithmetree again, because I was writing about it for senior seminar, and I thought to try this problem again.

I calculated out some small values (along with some small values of (a+b) choose a, for comparison) up to f(5,5), and I tried to see what I could make of it. And after a while of staring I noticed - these numbers in the first row (or column - obviously f is a symmetric function, both from the recursion and from the properties of Arithmetree; but I went by rows) are the odd numbers, and odd numbers are sums of two consecutive integers, which are the numbers found in the first row of my other chart... and these 1s in the 0th row, well they are the sums of 1 consecutive 1 in the 0th row of my other chart... are the numbers in the 2nd row perhaps the sums of 3 consecutive numbers in the second row of my other chart? No, they're not. But what if I count the middle one twice? Then it works. Ah, I see... I bet if I weight the next row 1 3 3 1... indeed, it works. And so, just from that, I managed to guess that

f(a,b)=sum from k=0 to b of (a+k choose b)(b choose k)

It was pretty late at night right then, and I didn't go to bed, so I didn't verify just then that it actually satisfied the recursion. I did that the next day (it turned out to be right) when Tom was around - "Oh, do I see n choose k symbols?" he said. I told him about the problem, and about my formula. (Actually at first I told him a misremembered formula, which was very wrong; but then I got it right.) Now, we both agreed, there was one big problem with it: While the function was certainly symmetric, this form didn't make it look symmetric at all. And then Tom did what I just hadn't thought of: he found f's generating function and got a symmetric formula immediately. :P

Yeah, I just *totally* never thought of that.

Anyway, his symmetric formula is

f(a,b)=1/2 sum from n=0 to ∞ of 1/2ⁿ*(n choose a)(n choose b)

Admittedly it's an infinite series, but if you actually want to calculate the function, the recursion is the best way to do that anyway. :P

So now, this still leaves a few questions. Such as, is there any better or combinatorial way of showing that my asymmetric sum is, in fact, symmetric? Can we actually find any combinatorial interpretation of f? (Sizes of sums of Arithmetrees does not count. :P )

That's pretty much where this stands.

-Sniffnoy