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.



The combinatorial interpretation of an identity found in "Primes in tuples I"
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](http://www.mat.univie.ac.at/~slc/wpapers/s54gessel.html), Séminaire Lotharingien de Combinatoire, B54b (2005), 10 pp.


