# Is there a combinatorial way to see the link between the beta and gamma functions?

The Wikipedia page on the beta function gives a simple formula for it in terms of the gamma function. Using that and the fact that $\Gamma(n+1)=n!$, I can prove the following formula: $$\begin{eqnarray*} \frac{a!b!}{(a+b+1)!} & = & \frac{\Gamma(a+1)\Gamma(b+1)}{\Gamma(a+1+b+1)}\\ & = & B(a+1,b+1)\\ & = & \int_{0}^{1}t^{a}(1-t)^{b}dt\\ & = & \int_{0}^{1}t^{a}\sum_{i=0}^{b}\binom{b}{i}(-t)^{i}dt\\ & = & \int_{0}^{1}\sum_{i=0}^{b}\binom{b}{i}(-1)^{i}t^{a+i}dt\\ & = & \sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\int_{0}^{1}t^{a+i}dt\\ & = & \sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\left[\frac{t^{a+i+1}}{a+i+1}\right]_{t=0}^{1}\\ & = & \sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\frac{1}{a+i+1}\\ b! & = & \sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\frac{(a+b+1)!}{a!(a+i+1)} \end{eqnarray*}$$ This last formula involves only natural numbers and operations familiar in combinatorics, and it feels very much as if there should be a combinatoric proof, but I've been trying for a while and can't see it. I can prove it in the case $a=0$: $$\begin{eqnarray*} & & \sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\frac{(b+1)!}{0!(i+1)}\\ & = & \sum_{i=0}^{b}(-1)^{i}\frac{b!(b+1)!}{i!(b-i)!(i+1)}\\ & = & b!\sum_{i=0}^{b}(-1)^{i}\frac{(b+1)!}{(i+1)!(b-i)!}\\ & = & b!\sum_{i=0}^{b}(-1)^{i}\binom{b+\text{1}}{i+1}\\ & = & b!\left(1-\sum_{i=0}^{b+1}(-1)^{i}\binom{b+\text{1}}{i}\right)\\ & = & b! \end{eqnarray*}$$ Can anyone see how to prove it for arbitrary $a$? Thanks!

• The usual interpretation of "combinatoric proof" (that I'm accustomed to) is to show that the beta function counts something; what exactly do you mean by "combinatoric proof" here? Oct 12, 2011 at 17:15
• In any event: it might be more interesting to establish this relationship instead... Oct 12, 2011 at 17:18
• I'm with @J.M. - your derivation for $a=0$ doesn't really look like a combinatorial proof, as you're using only symbolic manipulation instead of counting and combining objects.
– anon
Oct 12, 2011 at 21:03

Here's a combinatorial argument for $a!\, b! = \sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\frac{(a+b+1)!}{(a+i+1)}$, which is just a slight rewrite of the identity you want to show.

Suppose you have $a$ red balls numbered $1$ through $a$, $b$ blue balls numbered $1$ through $b$, and one black ball.

Question: How many permutations of the balls have all the red balls first, then the black ball, and then the blue balls?

Answer 1: $a! \,b!$. There are $a!$ ways to choose the red balls to go in the first $a$ slots, $b!$ ways to choose the blue balls to go in the last $b$ slots, and $1$ way for the black ball to go in slot $a+1$.

Answer 2: Let $A$ be the set of all permutations in which the black ball appears after all the red balls (irrespective of where the blue balls go). Let $B_i$ be the subset of $A$ such that the black ball appears after blue ball $i$. Then the number of permutations we're after is also given by $|A| - \left|\bigcup_{i=1}^b B_i\right|$. Since the probability that the black ball appears last of any particular $a+i+1$ balls is $\frac{1}{a+i+1}$, and there are $(a+b+1)!$ total ways to arrange the balls, by the principle of inclusion-exclusion we get $$\frac{(a+b+1)!}{a+1} - \sum_{i=1}^{b}\binom{b}{i}(-1)^{i+1}\frac{(a+b+1)!}{(a+i+1)} = \sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\frac{(a+b+1)!}{(a+i+1)}.$$

• Fantastic! How did you find this? Oct 12, 2011 at 22:17
• @Steven: I thought about it for way too long. :) More seriously, an alternating binomial sum smells like inclusion-exclusion to me. I also thought I could generalize my answer to a similar question, and that turned out to work, although it took a while to get the formulation right. I kept trying to apply inclusion-exclusion to the full set of permutations, and it finally hit me that I only needed to consider subsets of the set I call $A$. And thanks! Oct 12, 2011 at 22:30
• Nicely done indeed!
– robjohn
Oct 13, 2011 at 0:37
• @robjohn: And thanks for the edit. Not sure how I managed to leave that out! :) Oct 13, 2011 at 1:32
• Beautiful, this is exactly the kind of answer I was hoping for, thank you! Oct 13, 2011 at 7:04

Using partial fractions, we have that $$\frac{1}{(a+1)(a+2)\dots(a+b+1)}=\frac{A_1}{a+1}+\frac{A_2}{a+2}+\dots+\frac{A_{b+1}}{a+b+1}\tag{1}$$ Use the Heaviside Method; multiply $(1)$ by $(a+k)$ and set $a=-k$ to solve $(1)$ for $A_k$: $$A_k=\frac{(-1)^{k-1}}{(k-1)!(b-k+1)!}=\frac{(-1)^{k-1}}{b!}\binom{b}{k-1}\tag{2}$$ Plugging $(2)$ into $(1)$, yields $$\frac{a!}{(a+b+1)!}=\sum_{k=1}^{b+1}\frac{(-1)^{k-1}}{b!}\binom{b}{k-1}\frac{1}{a+k}\tag{3}$$ Multiplying $(3)$ by $b!$ and reindexing, gives us $$\frac{a!b!}{(a+b+1)!}=\sum_{k=0}^{b}(-1)^k\binom{b}{k}\frac{1}{a+k+1}\tag{4}$$ and $(4)$ is your identity.

Update: Starting from the basic binomial identity $$(1-x)^b=\sum_{k=0}^b(-1)^k\binom{b}{k}x^k\tag{5}$$ multiply both sides of $(5)$ by $x^a$ and integrate from $0$ to $1$: $$B(a+1,b+1)=\sum_{k=0}^b(-1)^k\binom{b}{k}\frac{1}{a+k+1}\tag{6}$$

• FYI: This argument appears on pages 188-189 of Concrete Mathematics, 2nd edition, where it is discussed in the context of the $n$th forward difference formula. Oct 12, 2011 at 20:50
• This identity is one of my favorite uses of partial fractions and it turns up when using Euler's Transform for series acceleration.
– robjohn
Oct 12, 2011 at 21:00
• @Mike: not surprising since it computes the $b^{th}$ forward difference of $\frac{1}{a+1}$. Thanks for the reference!
– robjohn
Oct 12, 2011 at 21:02

Seven years later I found another way to attack this. Define $$f(b, a) = \frac{a!b!}{(a+b+1)!}$$ and $$h(b, a) = \sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\frac{1}{a+i+1}$$. To connect the two, we define $$g$$ such that $$g(0, a) = \frac{1}{a + 1}$$ and $$g(b + 1, a) = g(b, a) - g(b, a + 1)$$ and prove by induction in $$b$$ that $$f = g = h$$. In each case the base case is straightforward and we consider only the inductive step.

$$\begin{eqnarray*} & & g(b + 1, a) \\ & = & g(b, a) - g(b, a + 1) \\ & = & f(b, a) - f(b, a + 1) \\ & = & \frac{a!b!}{(a+b+1)!} - \frac{(a+1)!b!}{(a+b+2)!} \\ & = & \frac{a!b!(a + b + 2)}{(a+b+2)!} - \frac{a!b!(a+1)}{(a+b+2)!} \\ & = & \frac{a!b!(b+1)}{(a+b+2)!} \\ & = & \frac{a!(b+1)!}{(a+b+2)!} \\ & = & f(b+1, a)\\ \end{eqnarray*}$$

$$\begin{eqnarray*} & & g(b + 1, a) \\ & = & g(b, a) - g(b, a + 1) \\ & = & h(b, a) - h(b, a + 1) \\ & = & \left(\sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\frac{1}{a+i+1}\right) - \left(\sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\frac{1}{a+i+2}\right) \\ & = & \frac{1}{a+1} + \left(\sum_{i=1}^{b}\binom{b}{i}(-1)^{i}\frac{1}{a+i+1}\right) - \left(\sum_{i=0}^{b-1}\binom{b}{i}(-1)^{i}\frac{1}{a+i+2}\right) - (-1)^{b}\frac{1}{a+b+2}\\ & = & \frac{1}{a+1} + \left(\sum_{i=1}^{b}\binom{b}{i}(-1)^{i}\frac{1}{a+i+1}\right) + \left(\sum_{i=1}^{b}\binom{b}{i-1}(-1)^{i}\frac{1}{a+i+1}\right) + (-1)^{b+1}\frac{1}{a+b+2}\\ & = & \frac{1}{a+1} + \left(\sum_{i=1}^{b}\left(\binom{b}{i} + \binom{b}{i-1}\right)(-1)^{i}\frac{1}{a+i+1}\right) + (-1)^{b+1}\frac{1}{a+b+2}\\ & = & \frac{1}{a+1} + \left(\sum_{i=1}^{b}\binom{b+1}{i}(-1)^{i}\frac{1}{a+i+1}\right) + (-1)^{b+1}\frac{1}{a+b+2}\\ & = & \sum_{i=0}^{b+1}\binom{b+1}{i}(-1)^{i}\frac{1}{a+i+1} \\ & = & h(b + 1, a) \\ \end{eqnarray*}$$