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

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.

• You don't need to assume anything about $n$; if $n \lt p$ then ${n \choose p} = \lfloor \frac{n}{p} \rfloor = 0$. Commented Oct 22, 2020 at 8:57
• Yes, indeed! I'll edit so. Commented Oct 22, 2020 at 9:02
• – Sil
Commented Oct 22, 2020 at 9:29

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$$.

• @cosmo: the argument uses almost no group theory but I suppose it's worth writing it out without the group theory. Commented Oct 22, 2020 at 9:04
• @cosmo: I wrote out the argument for $p = 3$ without the explicit references to group theory. Commented Oct 22, 2020 at 9:11
• So fixed orbits $123 \to 231 \to 312 \to 123$. Orbits of size $p$ : $124 \to 235 \to 316 \to 124$ and $125 \to 236 \to 314 \to 125$ This is the bijection! Commented Oct 22, 2020 at 9:38
• Yes, that's right. This is in general a surprisingly powerful method for proving congruences mod a prime bijectively. Commented Oct 22, 2020 at 9:43
• Very nice! Thank you for wonderful introduction to group theory and other things for me! :) Commented Oct 22, 2020 at 9:44