Combinatorial proof of the fact $p$ doesn't divide $ n \choose p^k$

Question

Let $p^k | n$ and $p^{k+1} \nmid n$. Is there any combinatorial proof of the fact that $p \nmid {n \choose p^{k}} $ ?

Answer 1

Here's one. I'm bad at describing combinatorics without pictures, so please comment if something doesn't make sense.

Consider arrangments in which $n$ different people sit at a circular table with $n$ places, and $p^k$ of them have plates in front of them. We count the number of such arrangments in two different ways.

First, trivially, we count ${n \choose p^k}$ such arrangements.

Second, partition all possible arrangments into groups of arrangements (equivalence classes, really) such that two arrangements belong to the same group iff one is just a rotation of the other. Then if some group contains, say, $m$ arrangements, we have $m | n$. Letting $n = p^k a$, this means that modulo $p$, we don't care about most groups, because most groups contribute a multiple of $p$ arrangements.

What groups do we care about? Well, we care about when $m | n = p^k a$ but $p \nmid m$. This implies $m | a$, which means arrangements in the group must be unchanged when rotated by $a$. The only arrangements unchanged under rotation by $a$ are those consisting of $p^k$ equally-spaced plates, and all such arrangements belong to the same group. This group contributes $a$ distinct equally-spaced arrangements, so the total number of arrangements is congruent to $a$ modulo $p$.

Thus, we have shown that $$ {p^k a \choose p^k} \equiv a \pmod {p} $$

In particular, if $p^{k+1} \nmid n$ we have that $p \nmid a$ so $$ p \nmid {n \choose p^k}. $$