Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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? – J. M. Oct 12 '11 at 17:15
In any event: it might be more interesting to establish this relationship instead... – J. M. Oct 12 '11 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 '11 at 21:03
up vote 15 down vote accepted

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)}.$$

share|cite|improve this answer
Fantastic! How did you find this? – Steven Stadnicki Oct 12 '11 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! – Mike Spivey Oct 12 '11 at 22:30
Nicely done indeed! – robjohn Oct 13 '11 at 0:37
@robjohn: And thanks for the edit. Not sure how I managed to leave that out! :) – Mike Spivey Oct 13 '11 at 1:32
Beautiful, this is exactly the kind of answer I was hoping for, thank you! – Paul Crowley Oct 13 '11 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} $$

share|cite|improve this answer
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. – Mike Spivey Oct 12 '11 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 '11 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 '11 at 21:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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