Jason (jcreed) wrote,

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

  • (no subject)

    Guy from Seattle team we've been working with showed up today at work; no matter how much I'm generally comfortable working with remote teams (and I…

  • (no subject)

    Sean's back in town --- good fun working with nonremote teammates.

  • (no subject)

    Sean's in town at work, good times.

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded