Combinatorial interpretation of this number? It is straightforward to show that if $m,n\in\mathbb{Z}$ and $m\geq n$, then
$$m\mid \gcd(m, n)\binom{m}{n}.$$
I'm trying to find a combinatorial interpretation of this fact, but I can't seem to come up with one. My two proofs are formal, and do not give me any combinatorial insight.
 A: $\mathbb Z/m$ acts (by transitions) on the set of $n$-element subsets of $\mathbb Z/m$. The action is not free but its restriction on any subgroup of order coprime to $n$ — in particular, on $\gcd(m,n)\mathbb Z/m\subset\mathbb Z/m$ — is free. So $\frac m{\gcd(m,n)}\mid\binom mn$.
A: Set $\gcd(m,n)=d$ and write $m=da, n=db$ where $\gcd(a,b)=1$.  Then your statement is equivalent to $$a\left|{da\choose db}\right.$$
Consider subsets of size $db$ from $S=\{0,1,2,\ldots, da-1\}$.  The permutation $\phi:S\rightarrow S$ given by $\phi(x)=x+d\pmod{da}$.  $\phi$ also induces a map on subsets of size $db$.  We may call two such subsets equivalent if we can get from one to another by iterating $\phi$.  Iterating $\phi$ $a$ times we get back to where we started, and in fact all the $a$ subsets must be distinct because $\gcd(a,b)=1$.  Hence the subsets of size $db$ have been partitioned into classes of size $a$, which proves the statement.
A: This isn't entirely combinatorial, but: 
We prove that $\begin{pmatrix} m \\ n \end{pmatrix}$ is always a multiple of $m/\gcd(m,n)$ using the left multiplication action of $\mathbb{Z}_m$ on the set $X$ of all its subsets of size $n$.  By definition, $|X|=\begin{pmatrix}m\\n\end{pmatrix}$.  By the theory of group actions, the set $X$ can be partitioned into orbits.  Then it is enough to show that every orbit must have size that is a multiple of $m/\gcd(m,n)$.  By the orbit stabilizer theorem, then, it is enough to prove that the stabilizer of a set $E$ of size $n$ must have a size that divides $\gcd(m,n)$.  
Let $E$ be a subset of $\mathbb{Z}_m$ of size $n$.  The stabilizer of $E$ is a subgroup of $\mathbb{Z}_n$, and all subgroups of $\mathbb{Z}_m$ are cyclic.  Furthermore, if we choose the minimal member $d$ of any subgroup of $\mathbb{Z}_m$, then $d$ generates that subgroup.  So let $d$ be the minimal generator of the stabilizer of $E$.  So the stabilizer of $E$ has size $m/d$, which means that we need to show that $m/d$ divides $\gcd(m,n)$.  
But if we choose an element $x$ of $E$, then the elements $x,x+d,x+2d,\dots$ all belong to $E$ as well (by the definition of a stabilizer); i.e., if $H$ is the stabilizer of $E$, then the coset $x+H$ is a subset of $E$.  So $E$ is a union of cosets of $H$, all of which have size $m/d$.  So $n$ is a multiple of $m/d$, which means that $m/d$ is a common factor of $m$ and $n$.  So $\gcd(m,n)$ divides $m/d$, as we wanted.  
