Combinatorial proof of $\sum_{k=0}^p {p \choose k}^2 {{n+2p-k}\choose {2p}} = {{n+p} \choose p}^2$

Question

(Valid for $n\geq p \geq 1$)

Basically, I'd like to exhibit two sets, one with cardinality ${{n+p} \choose p}^2$, another one with cardinality $\sum_{k=0}^p {p \choose k}^2 {{n+2p-k}\choose {2p}}$ and find a bijection between the two.

Defining $C_{k}^{n}$ as the subsets of $\left \{ 1,...,n \right \}$ with cardinality k, it is clear that $(C_{p}^{n+p})^{2}$ has a cardinality of ${{n+p} \choose p}^2$, and that $\bigcup_{k=0}^{p}\left ( (C_{k}^{p})^2 \times C_{2p}^{n+2p-k}\right )$ has a cardinality of $\sum_{k=0}^p {p \choose k}^2 {{n+2p-k}\choose {2p}}$, but I'm unable to find a bijection between the two sets.

Answer 1

The right-hand side counts the number of ways to choose two subsets $A,B$ of $[n+p]$, of size $p$ each. Let $t = |A \cap B|$, and write the $2p-t$ elements of $A \cup B$ in sequence: $\vec{x} = x_1,\ldots,x_{2p-t}$. Suppose that among the first $p$ elements, $p-k$ elements belong to $A$, forming a set $A'$, of which $\ell$ also belong to $B$, say of positions $i_1,\ldots,i_\ell$ inside $A'$. We add the elements $n+p+i_1,\ldots,n+p+i_\ell$ to $\vec{x}$. Among the $p-t$ elements $x_{p+1},\ldots,x_{2p-t}$, there are $p-k-\ell$ elements that belong to $B$, forming a set $B'$, of which $t-\ell$ also belong to $A$, say of positions $j_1,\ldots,j_{\ell-t}$ inside $B'$. We add elements number $j_1,\ldots,j_{\ell-t}$ of $\{n+p+1,\ldots,n+2p-t\} \setminus \{n+p+i_1,\ldots,n+p+i_\ell\}$ into $\vec{x}$.

After all the additions, $\vec{x}$ consists of $2p$ indices in $[n+2p-t]$. In order to decode $\vec{x}$ back into $A,B$, we need some additional information. First, we need to know which $p-k$ of $x_1,\ldots,x_p$ belong to $A$. Second, we need to know which $p-k$ of $x_{p+1},\ldots,x_{2p}$ belong to $B$; a chosen element beyond $[n+p]$ indicates an element of $B$ which comes from $A'$, and a non-chosen element beyond $[n+p]$ indicates an element of $A$ which which comes from $B'$. We have reached the left-hand side.

The confused reader might consider the following simpler identity first: $$ \sum_{k=0}^p \binom{p}{k}^2 \binom{n+p}{2p} = \binom{n+p}{p} \binom{n}{p}. $$ The right-hand side counts the number of ways to choose two disjoint subsets $A,B$ of $[n+p]$, each of size $p$. Given the $2p$ elements $x_1,\ldots,x_{2p}$ of $A \cup B$ and $k := |\{x_1,\ldots,x_p\} \cap B|$, we can decode $A,B$ given $\{x_1,\ldots,x_p\} \cap A$ (encoded as a subset of $[p]$ of size $p-k$) and $\{x_{p+1},\ldots,x_{2p} \cap B$ (encoded as a subset of $[p]$ of size $p-k$).

Answer 2

During the course of this proof I found that one can in fact show the more general result $$\sum_{k=0}^q {l+q\choose k}{p\choose q-k}{n+l+p+k\choose l+p+q}={n+l+p\choose l+p}{n+l+q\choose q}$$ from which the original result follows by setting $l=0$ and $p=q$.

We may show this by counting the number of ways to form a General Committee (GC) and a Women's Committee (WC) from a group of $l+q$ men and $n+l+p$ women, with the constraints that there are only women in WC and that there are exactly $l+p$ women in WC, and that the GC has exactly $q$ members.

First, we may simply choose $l+p$ women to be on the WC in ${n+l+p\choose l+p}$ ways; then we may choose $q$ from the remaining $n$ women and $l+q$ men to be on the GC in ${n+l+q\choose q}$ ways. Thus there are ${n+l+p\choose l+p}{n+l+q\choose q}$ ways to form the committees.

We may instead first specify how many of the $p$ oldest women on committees are on the WC. Call this number $q-k$. We may choose which of the $p$ oldest women on committees are in WC in ${p\choose q-k}$ ways.

Notice that there will be $l+p+q$ total people on committees. We now need to decide which people are on a committee, and which of the younger women (not among the p oldest) on committees are on the WC and we will have specified our committees (since the men on committees must be on the GC).

Associate with each man a distinct ticket with a number between $1$ and $l+q$, and choose $k$ of these tickets (in ${l+q\choose k}$ ways). Put these in a bucket with the names of each of the women and choose $l+p+q$ from the bucket to be on a committee (in ${n+l+p+k\choose l+p+q}$ ways). The men associated with any chosen tickets will be on the GC. Erase the number on each chosen ticket and shift down the numbers on all tickets with a higher number. We will decide which committee each of the chosen women are on using the unchosen tickets.

We know which committee each of the $p$ oldest women are on from the choice three paragraphs ago. Now, for each ticket left in the bucket, hand the ticket with the label $i$ to the $i$th youngest woman whose name was picked. The women with tickets are on the WC, and the rest (that are not among the $p$ oldest) are on the GC. Thus each committee is specified, and there are $${l+q\choose k}{p\choose q-k}{n+l+p+k\choose l+p+q}$$ ways to form them for a given $k$.

Some justification for that last paragraph: First note that there is no way for one of the $p$ oldest women on committees to receive a ticket (so they can not receive conflicting assignments). Because of the way we shifted down the tickets, the largest number that can be on an unchosen ticket is $l+q-j$, where $j$ is the number of chosen tickets. Since there were $l+q-j+p$ women chosen, these tickets can not be handed to the oldest $p$ (and could potentially be given to any of the women who are not the oldest $p$). Also notice each set of $k-j$ tickets left in the bucket produce a distinct choice of women for the WC; since the $j$ tickets picked from the bucket also produce distinct sets of men for the GC, we find that we may indeed choose each of our three sets independently. The correspondence above is also exhaustive; any committee fitting our constraints can be formed in a unique way from some choice of tickets put in the bucket, names drawn from the bucket, and assignments for the $p$ oldest women on committees.

Summing over $k$ gives us the identity above. It can be written more usefully as: $$\sum_{k=0}^{q} {m\choose k}{p-m+q\choose q-k}{w+k\choose p+q}={w\choose p}{w-p+m\choose q}$$ (I may rewrite this using these variables later as they are likely easier to understand.)