Pascal’s triangle has many fascinating properties. One of them is for any given prime number p, the number of k-element subsets (0< k < p) of a p-element set is divisible by p:
You can think for a while how would you prove it. There might well be an elementary combinatorial proof of , although I suspect that it would be rather long and tedious. Fortunately there exists a simple proof using a bit of algebra!:
If or , then equals , so the task is trivial. Suppose now that 1<k<p-1 we will use the following simple facts about a group G acting on a set X:
Fact 1. X is the disjoint union of the orbits of the action.
Fact 2. The size of an orbit divides the size of the group.
Once you know what is an action, the above facts are almost immediate. To prove , consider the multiplicative cyclic group of size ,
where is calculated mod p.
Let X be the set of all k-element subsets of and let G act on X by Let us show that the orbit of any contains more than one element. Suppose . Since 1< k < p-1, there are non-zero elements and . Moreover since G is a group, there exists such that if you think of m and n as elements of G. But this is the same as saying , so the orbit of A contains some set that is not A, i.e. we proved what we wanted.
By Fact 2, the orbit has exactly size p and so Fact 1 implies that |X| is divisible by p.