Combinatorial proof that $\sum_0^n {n+k \choose n}{2n-k-1 \choose n-1} = {3n \choose n}$

Question

I am trying to derive combinatorial proof of the following:

$$\sum_{k=0}^n {n+k \choose n}{2n-k-1 \choose n-1} = {3n \choose n}$$

I attempted the construction of argument of type "split the $3n$ elements into $n$ sections of $3$ elements each", and count how many ways it can be made, but I do not reach the desired statement. So I am not sure it is the right approach. I also fail to reach the conclusion using a grid path approach. Any help is appreciated!

Answer 1

HINT : consider discrete grid and then $\binom{n}{k}$ is number of ways to reach point $(n-k,k)$ if we start with point $(0,0)$. What can you say about $\binom{3n}{n}$ ? How can you reach point $(2n,n)$?

Answer 2

We first rewrite the identity slightly as

$$\sum_{k=0}^n\binom{n+k}n\binom{2n-k-1}{n-1}=\sum_{k=0}^n\binom{n+k}k\binom{2n-k-1}{n-k}\;.\tag{1}$$

I’ll show that the righthand side of $(1)$ counts the $n$-element subsets of $[3n]$ and is therefore equal to $\binom{3n}n$. Suppose that $S$ is such a set. For $k=0,\ldots,n$ let $s_k=|S\cap[n+k]|$.

Claim: There is a $k_S$ such that $0\le k_S\le n$, $|S\cap[n+k_S]|=k_S$, and $n+k_S+1\notin S$.

Proof of Claim: If $s_0=0$, we’re done, so suppose that $s_0>0$, and for $k=0,\ldots,n$ let $d_k=s_k-k$. Clearly $s_{k}-s_{k-1}\in\{0,1\}$ for $k\in[n]$, so $d_k\in\{d_{k-1},d_{k-1}-1\}$. Since $d_0>0$ and $d_n\le 0$ (since clearly $s_n\le n$), $\{k\in[n]:d_k=0\}\ne\varnothing$; let $k_S=\max\{k\in[n]:d_k=0\}$. Clearly $s_{k_S}=k_S$. If $k_S=n$, then $S\subseteq[n+k_S]$, and clearly $n+k_S+1\notin S$. If $k_S<n$, then $d_{k_S+1}=-1$, $s_{k_S+1}=s_{k_S}$, and again $n+k_S+1\notin S$. $\dashv$

For $k=0,\ldots,n$ there are $\binom{n+k}k$ ways to choose $k$ numbers from $[n+k]$ and $\binom{2n-k-1}{n-k}$ ways to choose $n-k$ numbers from $[3n]\setminus[n+k+1]$, so there are $\binom{n+k}k\binom{2n-k-1}{n-k}$ ways to choose an $n$-element $S\subseteq[3n]$ such that $k_S=k$. Summing over $k$ yields the identity.

Answer 3

Note that ${3n\choose n}={3n\choose 2n}$ is the number of subsets $A\subset\{1,2,3,\cdots,3n\}$ with $|A|=2n$, say $A=\{a_1,a_2,\cdots,a_{2n}\}$ with $a_1<a_2<\cdots<a_{2n}$.

This is another way to count them:

The range of possible values for $a_{n+1}$ is $n+1,\cdots,2n+1$. Suppose that $a_{n+1}=n+k+1$ for some $k\in\{0,1,2,\cdots,n\}$. We must have $$a_1,\cdots,a_n\in\{1,2,3,\cdots,n+k\}\qquad\qquad a_{n+2},\cdots,a_{2n}\in\{n+k+2,\cdots3n\}$$ Thus we have ${n+k\choose n}$ ways to pick $a_1,\cdots,a_n$ and ${2n-k-1\choose n-1}$ ways to pick $a_{n+2},\cdots,a_{2n}$, so ${n+k\choose n}{2n-k-1\choose n-1}$ ways in total.
If we sum over $k$ we get our answer: $$\sum_{k=0}^n {n+k\choose n}{2n-k-1\choose n-1}={3n\choose 2n}={3n\choose n}$$