Proving the identity $ \sum_{k=0}^{\min\{p,q\}} \binom{n}{k} \binom{n-k}{p-k} \binom{n-p}{q-k} = \binom{n}{p} \binom{n}{q}$

binomial-coefficientscombinatorial-proofscombinatoricssummation

While preparing for an exam, I am trying to prove the identity below. I searched for similar questions but only found Combinatorial proof of ${n\choose p}{n\choose q}=\sum_{k=0}^n {n \choose k}{n-k \choose p-k}{n-k \choose q-k}$
(Someone mentioned that this identity may be not true).

Question

Let $p,q ,n\in \mathbb{N}$ s.t $p,q \le n$

$$ \sum_{k=0}^{\min\{p,q\}} \binom{n}{k} \binom{n-k}{p-k} \binom{n-p}{q-k} = \binom{n}{p} \binom{n}{q}$$

My attempt

  • First of all, I want to find a combinatorial proof since it's important for me to understand the "combinatorial story" behind it.

  • I draw this in order to understand maybe what's the "story". But I'm stuck understanding what are the purple elements and the whole connection to the LHS (Note that the index k "runs" over vaules from $0$ to $\min{(p,q)}$). enter image description here

I would appreciate if someone here can try to continue my solution or suggest an alternative solution (if you do please explain each step the motivation behind it).

Best Answer

Disclaimer

Just a summary of your own attempt, comment by J.G., and answer by Robert Wegner

Set Up

There are $n$ people, choose $p$ to play football and choose $q$ to play volleyball. Some people may play both of them.

Right Hand Side

  • Choose $p$ out of $n$ to play football
  • Choose $q$ out of $n$ to play volleyball

The total number of possibilities is given by the right hand side.

Left Hand Side

  • Choose $k\in\left[0,\min{\left(p,q\right)}\right]$ to play both
  • From remaining $n-k$, choose $p-k$ to play only football
  • From remaining $n-p$, choose $q-k$ to play only volleyball

Summing up for all allowed value of $k$, the total number of possibilities is then given by the LHS.

Conclusion

Since both count the same object, RHS must equal LHS.

Related Question