The combinatorial interpretation of an identity found in “Primes in tuples I”

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.

1 Answer

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.