Combinatorial interpretation for $\binom{n}{3}- \lfloor \frac{n}{3} \rfloor$

Question

P2, RMO 2003, India

For any natural number $n\gt7$, prove that $\binom{n}{7}-\lfloor \frac{n}{7} \rfloor$ is divisible by $7$.

My algebraic solution :

$$ \binom{n}{7} = \dfrac{n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)}{7\cdot6!} $$

One of the numbers in numerator is $7 \lfloor \frac{n}{7} \rfloor$ and product of rest is $6!$ modulo $7$. Done.

But obviously this statement generalizes :

For any prime $p$, $\binom{n}{p}-\lfloor \frac{n}{p} \rfloor$ is always divisible by $p$.

I checked this on diagonals of Pascal's triangle for small $p$ and found it is true.

So I am looking for its combinatorial meaning.

I tried looking for a bijective proof for $p=3$. Consider all $3$-subsets of $\{1,2,3,\ldots,n\}$. Take away certain $\lfloor n/3 \rfloor$ subsets. Remainder is clearly divisible into three groups. But which $\lfloor n/3 \rfloor$ subsets? I'm not able to proceed.

Any help is appreciated. Thank you!

Sorry for not phrasing this property properly. It's because I'm lacking insights.

Answer 1

The bijective argument for all $p$ is the following. Write $n = ap + b$ where $0 \le b \le p-1$, so that $a = \lfloor \frac{n}{p} \rfloor$. Divide the set $[n] = \{ 1, 2, \dots n \}$ into $a$ groups of $p$ elements and $b$ elements left over. Consider the action of the cyclic group $C_p$ on the set of $p$-element subsets of $n$ by cyclic permutation on each of the $a$ groups of $p$ elements. There are two kinds of orbits, orbits of size $p$ and fixed points, so ${n \choose p}$ is congruent $\bmod p$ to the number of fixed points. And the fixed points are exactly given by the $a$ groups of $p$ elements themselves, of which there are $a = \lfloor \frac{n}{p} \rfloor$.

A generalization of this argument proves that

$${ap + b \choose cp + d} \equiv {a \choose c} {b \choose d} \bmod p$$

and iterating this identity proves Lucas' theorem

$${\sum a_i p^i \choose \sum b_i p^i} \equiv \prod {a_i \choose b_i} \bmod p$$

where $a_i, b_i$ are digits in base $p$; this can also be proven directly with a similar argument. You can see several other arguments like this at this blog post, including a bijective proof of Fermat's little theorem and Wilson's theorem.

An important corollary of this result is that if $p^k$ is the largest power of $p$ dividing $n$ then ${n \choose p^k}$ is not divisible by $p$ (which also follows from Kummer's theorem). This fact can famously be used to prove the first Sylow theorem.

---

Edit: Stripping out the group theory, here is the argument specialized to the case $p = 3$ for concreteness but there's nothing special about $3$ here. Write $n = 3a + b$ where $0 \le b \le 2$. Divide the set $[n] = \{ 1, 2, \dots 3a + b \}$ into $a$ groups of $3$ elements

$$\{ 1, 2, 3 \}, \{ 4, 5, 6\}, \dots \{3a-2, 3a-1, 3a \}$$

together with $b$ leftover elements $\{ 3a+1, \dots 3a+b \}$. Now we are going to group together the $3$-element subsets of $\{ 1, 2, \dots 3a+b \}$ as follows:

• There are $a$ special $3$-element subsets given by the groups $\{ 1, 2, 3 \}, \{ 4, 5, 6 \}$, etc. we just picked.
• All of the other $3$-element subsets can be organized into groups of $3$ as follows. Consider the function $f : [n] \to [n]$ which "rotates" each of the $3$-element sets by adding $1 \bmod 3$ to each of them; that is, $f(1) = 2, f(2) = 3, f(3) = 1, f(4) = 5, f(5) = 6, f(6) = 4$, etc. $f$ does not do anything to the "remainder" $\{ 3a+1, \dots 3a+b \}$. Then every $3$-element subset $\{ i, j, k \}$ not of the above form is matched up with exactly two other $3$-element subsets $\{ f(i), f(j), f(k) \}, \{ f(f(i)), f(f(j)), f(f(k)) \}$ under the action of $f$. For example, $\{ 1, 2, 4 \}$ is matched up with $\{ 2, 3, 5 \}$ and $\{ 3, 1, 6 \}$. The $a$ special $3$-element subsets are exactly the subsets with the property that $\{ i, j, k \} = \{ f(i), f(j), f(k) \}$, so they don't get matched up with anything by $f$.

The general result, again stripped of any explicit references to group theory, is the following. Suppose $p$ is a prime, $X$ is a finite set, and $f : X \to X$ is a permutation such that $f^p(x) = x$ for all $x \in X$. Then $X$ splits up as the disjoint union of the fixed points of $f$ together with subsets of size $p$ of the form $\{ x, f(x), f^2(x), \dots f^{p-1}(x) \}$; in particular, $|X|$ is congruent to the number of fixed points of $f$, $\bmod p$.