### (no subject)

I was poking around with generating functions trying to get at *why* the number-of-paths formulas in http://jcreed.org/graphics/pebbles work the way they do. I only managed to get at them at the time by imitating the reasoning in the Kauffman-Noyes paper --- over lunch I tried getting to them from scratch by doing generatingfunction reasoning from the bare recurrences that define inductively what it means to count paths, and I got stumped at proving the following identity

(a choose c)(b choose c) = sum_n (n choose n-a,n-b,c,a+b-n-c) (-1)^(a+b-n-c)

(where (x choose y, z, ... w) is the multinomial coefficient x!/(y!z!...w!) where it must be that y+z+...+w = x for the notation to make sense)

It sure seems to be true for a half-dozen small expamples I tried, but I can't get any traction trying to prove it in any intuitively sensible way.

(a choose c)(b choose c) = sum_n (n choose n-a,n-b,c,a+b-n-c) (-1)^(a+b-n-c)

(where (x choose y, z, ... w) is the multinomial coefficient x!/(y!z!...w!) where it must be that y+z+...+w = x for the notation to make sense)

It sure seems to be true for a half-dozen small expamples I tried, but I can't get any traction trying to prove it in any intuitively sensible way.