14
$\begingroup$

I am trying to find an combinatorial interpretation for the following combinatorial identity involving iterated binomial coefficients, which appeared in the November 1980 edition of The American Math Monthly:

$\dbinom{\binom{n}{b}}{2}=\displaystyle\sum_{j=1}^b\dbinom{\binom{b}{j}+e_j}{2}\binom{n+b-j}{2b},$

where $e_j=\frac{1+(-1)^{j+1}}{2}$, that is, $e_j=1$ if $j$ is odd, and $0$ otherwise.

Essentially, the left hand side of the identity can be interpreted as the number of ways to choose 2 $b$-element subsets of $\{1,2,\cdots,n\}$. What I am interested in is the derivation of the right hand side of the identity; I have read the proof in The American Math Monthly, and the author mentioned that the expression $\binom{n+b-j}{2b}$ refers to the selection of $2b$ objects from the original set $\{1,2,\cdots,n\}$, augmented by the adjunction of $b-j$ "jokers", where $0\leq j\leq b-1$, to allow for the fact that the intersection of two distinct $b$-element subsets of $\{1,2,\cdots,n\}$ can have a minimum and a maximum cardinality of $0$ and $b-1$ respectively.

What I am struggling to understand here is the expression $\dbinom{\binom{b}{j}+e_j}{2}$; how does one interpret this expression? Alternatively, is there any other way for which one can prove the identity? Personally, I have proven via a combination of combinatorial and algebraic methods that the identity does hold for small values of $b$, but the expression is not that tractable for large values of $b$.

$\endgroup$
  • $\begingroup$ $$\dbinom{\binom{b}{j}+e_j}{2}$$ can be expressed as $$\frac{1}{8} \left(-2 \binom{b}{j}+(-1)^j-1\right) \left(-2 \binom{b}{j}+(-1)^j+1\right)$$ The whole expression can also be expressed in the form of hypergeometric functions. $\endgroup$ – martin Apr 13 '15 at 21:40
8
+50
$\begingroup$

Suppose we seek to evaluate (the term for $j=0$ is zero) $$\frac{1}{2} \sum_{j=0}^b \left({b\choose j} + e_j\right) \left({b\choose j} + e_j-1\right) {n+b-j\choose 2b}.$$

This sum has four components, call them $A,B,C$ and $D.$

We have $$A = \frac{1}{2} \sum_{j=0}^{b/2} {b\choose 2j}^2 {n+b-2j\choose 2b},$$ and $$B = - \frac{1}{2} \sum_{j=0}^{b/2} {b\choose 2j} {n+b-2j\choose 2b},$$ and $$C = \frac{1}{2} \sum_{j=0}^{b/2} {b\choose 2j+1}^2 {n+b-2j-1\choose 2b},$$ and finally $$D = \frac{1}{2} \sum_{j=0}^{b/2} {b\choose 2j+1} {n+b-2j-1\choose 2b}.$$

Starting with $A$ we put (we will use this substitution several times with different values of $b$ and $j$)

$${b\choose 2j} = \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z^{2j+1}} \; dz$$

to get for the sum $$\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z} \sum_{j=0}^{b/2} {b\choose 2j} {n+b-2j\choose 2b} \frac{1}{z^{2j}} \; dz.$$

For the inner sum we get $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n+b}}{w^{2b+1}} \sum_{j=0}^{b/2} {b\choose 2j} \frac{1}{z^{2j}(1+w)^{2j}} \; dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n+b}}{w^{2b+1}} \left(\left(1+\frac{1}{z(1+w)}\right)^b + \left(1-\frac{1}{z(1+w)}\right)^b\right) \; dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1} z^b} \left(\left(z+zw+1\right)^b + \left(z+zw-1\right)^b\right) \; dw .$$

This lets us evaluate $B$ which has $z=1$ to obtain $$-\frac{1}{4} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \left(\left(w+2\right)^b + \left(w\right)^b\right) \; dw.$$

We get for $C$ the integral $$\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z} \sum_{j=0}^{b/2} {b\choose 2j+1} {n+b-2j-1\choose 2b} \frac{1}{z^{2j+1}} \; dz.$$

The inner sum here evaluates to $$\frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1} z^b} \left(\left(z+zw+1\right)^b - \left(z+zw-1\right)^b\right) \; dw .$$

This lets us evaluate $D$ which has $z=1$ to obtain $$+\frac{1}{4} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \left(\left(w+2\right)^b - \left(w\right)^b\right) \; dw.$$

It follows that $B+D$ is $$-\frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} w^b\; dw = -\frac{1}{2} {n\choose b}.$$

On the other hand $A+C$ is $$\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1} z^b} \left(z+zw+1\right)^b \; dw \; dz \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \left(\frac{1+z}{z}+w\right)^b \; dw \; dz.$$

This is $$\frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z} \sum_{q=0}^b {b\choose q} \left(\frac{1+z}{z}\right)^q w^{b-q} \; dz \; dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \frac{1}{2\pi i} \int_{|z|=\gamma} \sum_{q=0}^b {b\choose q} \frac{(1+z)^{b+q}}{z^{q+1}} w^{b-q} \; dz \; dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \sum_{q=0}^b {b\choose q} {b+q\choose q} w^{b-q} \; dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \sum_{q=0}^b {b\choose q} {b+q\choose q} \frac{(1+w)^{n}}{w^{b+q+1}} \; dw.$$

This finally yields $$\frac{1}{2} \sum_{q=0}^b {b\choose q} {b+q\choose q} {n\choose b+q} = \frac{1}{2} \sum_{q=0}^b {b\choose q} \frac{n!}{b!q!(n-b-q)!} \\ = \frac{1}{2} {n\choose b} \sum_{q=0}^b {b\choose q} \frac{(n-b)!}{q!(n-b-q)!} = \frac{1}{2} {n\choose b} \sum_{q=0}^b {b\choose q} {n-b\choose q} \\ = \frac{1}{2} {n\choose b} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n-b}}{v} \sum_{q=0}^b {b\choose q} \frac{1}{v^q} \; dv \\ = \frac{1}{2} {n\choose b} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n-b}}{v} \left(1+\frac{1}{v}\right)^b \; dv \\ = \frac{1}{2} {n\choose b} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n}}{v^{b+1}} \; dv = \frac{1}{2} {n\choose b}^2.$$

The conclusion is that $$A+B+C+D = \frac{1}{2} {n\choose b}^2 - \frac{1}{2} {n\choose b} = \frac{1}{2} {n\choose b} \left({n\choose b}-1\right),$$

which was to be shown.

Another instance of the Egorychev method is at this MSE link.

Addendum Tue Apr 14 21:38:00 CEST 2015. As per the comments we can evaluate $B+D$ as follows. $$B+D = -\frac{1}{2} \sum_{j=0}^b {b\choose j} (-1)^j {n+b-j\choose 2b}.$$

Using the standard integral substitution from above this yields $$-\frac{1}{2} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n+b}}{v^{2b+1}} \sum_{j=0}^b {b\choose j} (-1)^j \frac{1}{(1+v)^j}\; dv \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n+b}}{v^{2b+1}} \left(1-\frac{1}{1+v}\right)^b \; dv \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n+b}}{v^{2b+1}} \left(\frac{v}{1+v}\right)^b \; dv \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n}}{v^{b+1}} \; dv = -\frac{1}{2}{n\choose b}.$$

$\endgroup$
  • $\begingroup$ I quite like your solution of using complex analytic methods to prove the identity. However, I do realise that all we want to show is that $\sum_{j=0}^b\binom{b}{j}^2\binom{n+b-j}{2b}=\binom{n}{b}^2$ and $\sum_{j=0}^b(-1)^{j+1}\binom{b}{j}\binom{n+b-j}{2b}=\binom{n}{b}$. Out of curiosity more than anything else, is there a combinatorial way of proving these identities? $\endgroup$ – yoshi Apr 14 '15 at 8:41
  • $\begingroup$ Nice and clear presentation! +1 $\endgroup$ – Markus Scheuer Apr 14 '15 at 9:46
  • 2
    $\begingroup$ It is not as simple as it could be, but I leave additional simplification to the reader. $\endgroup$ – Marko Riedel Apr 14 '15 at 19:02
  • $\begingroup$ The two identities mentioned in @yoshi's comment above have since been corrected and proved at math.stackexchange.com/questions/1234156/… . (Just adding this comment for future readers' sake.) $\endgroup$ – darij grinberg Nov 23 '18 at 20:46
1
$\begingroup$

Here is an answer using formal power series that is somewhat simpler than the first one. We start as before:

$$\frac{1}{2} \sum_{j=0}^b \left({b\choose j} + e_j\right) \left({b\choose j} + e_j-1\right) {n+b-j\choose 2b}$$

where we have $e_j = [[j\;\text{is odd}]].$

Expanding we get three pieces, the first is

$$A = \frac{1}{2} \sum_{j=0}^b {b\choose j}^2 {n+b-j\choose 2b},$$

the second is

$$B = \frac{1}{2} \sum_{j=0}^b {b\choose j} (2e_j-1) {n+b-j\choose 2b} = \frac{1}{2} \sum_{j=0}^b {b\choose j} (-1)^{j+1} {n+b-j\choose 2b} $$

and the third

$$C = \sum_{j=0}^b e_j (e_j-1) {n+b-j\choose 2b} =0,$$

which leaves $A$ and $B.$ Starting with $A$ we observe that we must have $n\ge b$ or else the third binomial coefficient vanishes for all $j$ in the range, making for a zero contribution. We find

$$\frac{1}{2} \sum_{j=0}^b {b\choose j} [z^{b-j}] (1+z)^b [w^{n-b-j}] (1+w)^{n+b-j} \\ = \frac{1}{2} [z^b] (1+z)^b [w^{n-b}] (1+w)^{n+b} \sum_{j=0}^b {b\choose j} z^j w^j (1+w)^{-j} \\ = \frac{1}{2} [z^b] (1+z)^b [w^{n-b}] (1+w)^{n+b} \left(1+\frac{wz}{1+w}\right)^b \\ = \frac{1}{2} [z^b] (1+z)^b [w^{n-b}] (1+w)^{n} (1+w+wz)^b.$$

Recalling that $n\ge b$ this becomes

$$\frac{1}{2} [z^b] (1+z)^b [w^{n-b}] (1+w)^{n} \sum_{q=0}^b {b\choose q} w^q (1+z)^q \\ = \frac{1}{2} [z^b] (1+z)^b \sum_{q=0}^b {b\choose q} {n\choose n-b-q} (1+z)^q \\ = \frac{1}{2} \sum_{q=0}^b {b\choose q} {n\choose n-b-q} {b+q\choose b}.$$

Factoring the two binomials on the right we get

$$\frac{n!}{(n-b-q)! \times b! \times q!} = {n\choose b} {n-b\choose q}.$$

We continue with

$$\frac{1}{2} {n\choose b} \sum_{q=0}^b {b\choose q} {n-b\choose q} = \frac{1}{2} {n\choose b} \sum_{q=0}^b {b\choose q} [z^{n-b-q}] (1+z)^{n-b} \\ = \frac{1}{2} {n\choose b} [z^{n-b}] (1+z)^{n-b} \sum_{q=0}^b {b\choose q} z^q = \frac{1}{2} {n\choose b} [z^{n-b}] (1+z)^{n-b} (1+z)^b \\ = \frac{1}{2} {n\choose b}^2.$$

The piece labeled $B$ is next. We get

$$\frac{1}{2} \sum_{j=0}^b {b\choose j} (-1)^{j+1} [w^{n-b-j}] (1+w)^{n+b-j} \\ = - \frac{1}{2} [w^{n-b}] (1+w)^{n+b} \sum_{j=0}^b {b\choose j} (-1)^{j} w^j (1+w)^{-j} \\ = - \frac{1}{2} [w^{n-b}] (1+w)^{n+b} \left(1-\frac{w}{1+w}\right)^b \\ = - \frac{1}{2} [w^{n-b}] (1+w)^{n} = - \frac{1}{2} {n\choose b}.$$

We have shown that

$$A+B = \frac{1}{2} {n\choose b}^2 - \frac{1}{2} {n\choose b} = \frac{1}{2} {n\choose b} \left({n\choose b} - 1\right)$$

as claimed.

Remark. The piece $B$ was also evaluated in the first answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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