Proving expression with binomial coefficients is integer How do we prove that $\frac{\binom{n+1}{m+1}\binom{n}{m-1}}{m}$ for $n\ge m\ge1$ is an integer?
Both coefficients in the numerator are integers and the interval from $n+1$ to $n-m+2$ covered by the numerators of the binomial coefficients has length $m$. However, that doesn't guarantee the whole thing is an integer because those factors could be canceled by the denominators of the binomial coefficients that are not relatively prime to m.
If $m$ is prime then it's more obviously an integer because if the $m$ in the denominator of $\binom{n+1}{m+1}$ divides $n+1$ then the $m$ in the denominator of the whole expression cancels $n-m+2$, and otherwise, there are two multiples in the numerator. But how do we work with non-primes?
I also tried a counting argument but couldn't get anywhere with that.
 A: Use
$$
\frac{\binom{n+1}{m+1}\cdot\binom{n}{m-1}}{m}=\frac{\frac{n+1}{m+1}\binom{n}{m}\cdot\frac{m}{n+1}\binom{n+1}{m}}{m}
$$
and the fact that $m$ and $m+1$ are relatively prime.
Added: One can, in retrospect, devise a combinatorial interpretation. Define two sets:

*

*$A$ is the set of pairs of words, the first word of the pair an $(n+1)$-letter word with $n-m$ $X$s and $m+1$ $Y$s, one of the $Y$s underlined, and the second word of the pair an $n$-letter word with $n-m+1$ $x$s and $m-1$ $y$s;

*$B$ is the set of pairs of words, the first word of the pair an $n$-letter word with $n-m$ $X$s and $m$ $Y$s, and the second word of the pair an $(n+1)$-letter word with $n-m+1$ $x$s and $m$ $y$s, one of the $y$s underlined.

There is a bijective map from $A$ to $B$ that deletes the underlined $Y$ from the first word and inserts an underlined $y$ at the corresponding position in the second word. So $A$ and $B$ are of equal size, which gives combinatorial meaning to
$$
(m+1)\binom{n+1}{m+1}\binom{n}{m-1}=m\binom{n}{m}\binom{n+1}{m}.
$$
Because $m$ and $m+1$ have no common factor, both sides are divisible by $m(m+1)$.
A: Write this as
$$
\begin{aligned}
\color{blue}{\frac{1}{m}}\binom{n+1}{m+1}\color{blue}{\binom{n}{m-1}}
&=\color{blue}{\frac1{n+1}}\binom{n+1}{m+1}\color{blue}{\binom{n+1}{m}}
\\
&=\frac{m+1}{n+1}\binom{n+1}{m+1}\binom{n+1}{m}-\frac{m}{n+1}\binom{n+1}{m+1}\binom{n+1}{m}
\end{aligned}
$$
then apply the absorption identity to each summand.
