3
$\begingroup$

We all know the standard recurrence relation for binomial coefficients: $$ \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k} $$ Is there any finite-step recurrence relation one can write down for a product of binomials such as: $$ f(n,k) = \binom{n}{k}\binom{m-n}{k} $$ where $ m$ is a constant. A related question is: for gaussian distributions, the product of two gaussians is once again a gaussian. Is there such a relation for the product of binomial coefficients, possibly in terms of $\Gamma$ functions?

Thank you!

EDIT: Thanks for the hints! Unfortunately one key requirement is that the recurrence relation does not involve factors of $ n $, $ k $ or $ m$ explicitly.

$\endgroup$
2
  • $\begingroup$ Is $m$ to remain an absolute constant, or would you also be interested in a recursive way to compute $g(n,m,k)$ which would denote your $f(n,k)$ but with the $m$ thrown in as a third parameter? $\endgroup$
    – coffeemath
    Jun 1, 2014 at 2:40
  • $\begingroup$ Sure, if it makes it easier, we can let $ m$ vary. $\endgroup$
    – user154493
    Jun 1, 2014 at 2:51

3 Answers 3

1
$\begingroup$

There are a number of identities involving products of binomial coefficients or sums of products of binomial coefficients.

There's the (perhaps trivial)

$$\binom{n}{h}\binom{n-h}{k}=\binom{n}{k}\binom{n-k}{h}$$

One quite useful one is the Chu-Vandermonde identity

$${m+n \choose r}=\sum_{k=0}^r{m \choose k}{n \choose r-k}$$

for non-negative integer $m$,$n$ and $r$.

You can find a few additional results in the Wikipedia article on binomial coefficients.

I don't think these directly solve your problem though.

$\endgroup$
0
$\begingroup$

There is a "recursion" $f(n,0)=1$ and $$f(n,k+1)=\frac{(m-n-k)(n-k)}{(k+1)^2}\cdot f(n,k),$$ which can be shown using the factorial versions of the binomial coefficients. (If one doesn't like starting at $k=0$ can use $f(n,1)=(m-n)n$ to start out.)

$\endgroup$
0
$\begingroup$

$f(n,k)=\dfrac{n!(m-n)!}{k!(n-k)!(m-n-k)!(k)!}$

$f(n+1,k)=\dfrac{(n+1)!(m-n-1)!}{k!(n-k)!(m-n-k-1)!(k!)}$

From here $f(n+1,k)=\dfrac{f(n,k)(n+1)(m-n-k)}{(m-n)}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.