Prove using combinatorics $n \mid \binom{n}{m} \binom{n}{m-1}$

Prove using combinatorics $$n ~\Bigg | \binom{n}{m} \binom{n}{m-1}.$$

We should find a problem whose answer is $\displaystyle\dfrac{\displaystyle\binom{n}{m} \binom{n}{m-1}}{n \times f(n,m)}$ but I can't find such problem. Any hints?

Solution 1:

I am assuming you mean that $m$ is an integer between $1$ and $n$, inclusive.

Let $S$ be the set of pairs consisting of an $m$-element subset of $\{1,\ldots,n\}$ and an $(m-1)$-element subset of $\{1,\ldots,n\}$. Write an element of $S$ as a pair $(\{a_1,\ldots,a_m\},\{b_1,\ldots,b_{m-1}\})$, where $a_i,b_i\in \{1,\ldots,n\}$ for all $i$ and the $a_i$ elements are distinct from one another as are the $b_i$ elements.

Given such a pair, we can cyclically increment each of its entries by $1$ to obtain the new pair $(\{a_1+1,\ldots,a_m+1\},\{b_1+1,\ldots,b_{m-1}+1\}).$ Here the addition is modulo $n$.

After performing the cyclic increment $n$ times, we return to the pair we started with. Moreover, each of the $n$ pairs encountered along the way must be distinct from one another. To see why this is true, suppose to the contrary that after $k$ cyclic shifts, $1\leq k<n$, we return to the same pair we had started with. The only way this can happen is if both $km$ and $k(m-1)$ are multiples of $n$. But then their difference, $k$, would also have to be a multiple of $n$, which is a contradiction.

Thus, we have found a way of partitioning the elements of $S$ into sets of size $n$, so $n$ divides $|S|$. On the other hand, $|S|=\binom{n}{m}\binom{n}{m-1}$. This produces the desired combinatorial proof of the fact that $n$ divides $\binom{n}{m}\binom{n}{m-1}$.

EDIT: Allow me to clarify a key point in the proof above, in order to answer a question that was asked in the comments below. The reason why $km$ and $k(m-1)$ must be multiples of $n$ can be seen by considering the sums $a_1+\cdots+a_m$ and $b_1+\cdots+b_{m-1}$ modulo $n$. Each time an increment is performed, the sums increase by $m$ and $m-1$ modulo $n$, respectively. Thus if the pair returns to its starting value after $k$ cyclic shifts, then since the sums incremented by $km$ and $k(m-1)$ modulo $n$ during this time, we must have that both $km$ and $k(m-1)$ are multiples of $n$.

(One can consider the case $m=3$ to gain some intuition for what is going on.)

Solution 2:

Maybe this is not a combinatorial proof, but $$\frac{1}{n}\,\binom{n}{m}\,\binom{n}{m-1}=\binom{n-1}{m-1}\,\binom{n+1}{m}-\binom{n}{m}\,\binom{n}{m-1}\,.$$ This is because $$\begin{align*}\frac{1}{n}\,\binom{n}{m}\,\binom{n}{m-1}&=\frac{1}{m}\,\binom{n-1}{m-1}\,\binom{n}{m-1}\\&=\frac{1}{n+1}\,\binom{n-1}{m-1}\,\binom{n+1}{m}\,.\end{align*}$$ The above result is due to the identity $\displaystyle\binom{k}{r}=\frac{k}{r}\,\binom{k-1}{r-1}$, which has a combinatorial proof.