MathOverflow is a question and answer site for professional mathematicians. 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

I am currently reading the paper

D.A. Goldston, J. Pintz, C.Y. Yildirim, $\textit{Primes in tuples I}$, Annals of Mathematics $\textbf{170}$ (2009), 819-862

and in particular I found equation (8.16), which records the identity

$$\displaystyle \frac{1}{u!} \sum_{i=0}^u (-1)^i \binom{u}{i} \frac{d(d+1)\cdots(d+i-1)}{(v+d+i)!} = \frac{1}{(u+v+d)!} \binom{u+v}{u}$$

to be interesting. This identity itself admits a rather elegant proof via the Chu-Vandermonde identity.

I am interested in a suitable combinatorial interpretation for this identity, preferably an elementary counting argument.

Any insight would be appreciated.

share|cite|improve this question
up vote 12 down vote accepted

Since the terms aren't integers we can't find a combinatorial interpretation directly.

If we multiply both sides by $(u+v+d)!$ and rearrange, we can rewrite the identity as $$ \sum_{i=0}^u (-1)^i \binom{u+v+d}{u-i}\binom{d+i-1}{i} =\binom{u+v}{u}, $$ which we can interpret combinatorially. Let $U$, $V$, and $D$ be disjoint sets of sizes $u$, $v$, and $d$, and suppose that $D$ is totally ordered. Then $(-1)^i\binom{u+v+d}{u-i}\binom{d+i-1}{i}$ counts ordered pairs $(X,Y)$ where $X$ is a $(u-i)$-subset of $U\cup V \cup D$ and $Y$ is an $i$-multisubset of $D$ (i.e., a selection of $i$ elements of $D$ with unlimited repetition), with sign $(-1)^i$. The right side counts such pairs with $i=0$ in which $X$ contains no elements of $D$. All other such pairs can be canceled by a sign-reversing involution: In any other pair $X$ or $Y$ contains an element of $D$. Let $\delta$ be the least element of $D$ occurring in $X$ or $Y$. If $\delta$ occurs in $X$, move it from $X$ into $Y$. If $\delta$ does not occur in $X$, move one copy of $\delta$ from $Y$ into $X$.

Alternatively, we may multiply both sides by $u!\, (v+d)!$ and rewrite the identity as $$ \sum_{i=0}^u (-1)^i \binom u i \frac{(d)_i}{(d+v+1)_i} = \frac{(v+1)_u}{(d+v+1)_u}, $$ where $(a)_j = a(a+1)\cdots (a+j-1)$. A probabilistic proof of this identity, using inclusion-exclusion and the Pólya-Eggenburger urn model can be found in section 5 of my paper Symmetric Inclusion-Exclusion, Séminaire Lotharingien de Combinatoire, B54b (2005), 10 pp.

share|cite|improve this answer

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.