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?
 A: 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.
A: 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.)
A: Let $T:={n\choose k}\cdot{n\choose k+1}$
$A:={n-1\choose k}$, $B:=A\cdot n$ with $0 \leq k < n$).
Then ${n\choose k} = B/(n-k)$, ${n\choose k+1}= B/ (k+1)$
then $(n-k)$ and  $(k+1)$ divide $B=A\cdot n$ and $T= (B\cdot B)/(k+1)(n-k)$.
If $p$ is a prime  with $p|(n-k)$ and $p|(k+1)$ then $p| n+1=(n-k)+(k+1)$, then $p\not| n$ (otherwise $p|(n+1)-n=1$), then $p|A$, multiplying (with its multiplicity) such  primes we get a  $P\in N$, such that
$$P|A,\  (n-k)= P\cdot x,\ k+1= P\cdot y$$
with $x, y\in N$ coprime, if $A':= A/P$ follow that $x|A'\cdot n,\ y|A'\cdot n$ then (being $x, y$ coprime) $x\cdot y| A'n$.
From  $T= (A'\cdot P\cdot n\cdot A'\cdot P\cdot n)/(P\cdot x\cdot P\cdot y)=
(A'\cdot n)/(x\cdot y) \cdot  A'\cdot n$ we get the conclusion.
