6
$\begingroup$

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.

$\endgroup$

1 Answer 1

13
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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