Using Abstract Algebra To Understand Basic Combinatorics

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:

[tex]p | \binom{p}{k}\qquad \qquad \qquad (*)[/tex]

You can think for a while how would you prove it. There might well be an elementary combinatorial proof of [tex](*)[/tex], although I suspect that it would be rather long and tedious. Fortunately there exists a simple proof using a bit of algebra!:

If [tex]k=1[/tex] or [tex]k=p-1[/tex], then [tex]\binom{p}{k}[/tex] equals [tex]p[/tex], 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 [tex](*)[/tex], consider the multiplicative cyclic group of size [tex]p-1[/tex],
[tex]G=\mathbb{F}_p^*=\langle\{1,\dots,p-1\},\cdot\rangle[/tex]
where [tex]m\cdot n[/tex] is calculated mod p.

Let X be the set of all k-element subsets of [tex]\{0,\dots,p-1\}[/tex] and let G act on X by [tex]gA=\{ga\mid a\in A\}.[/tex] Let us show that the orbit of any [tex]A\in X[/tex] contains more than one element. Suppose [tex]A\in X[/tex]. Since 1< k < p-1, there are non-zero elements [tex]m\in A[/tex] and [tex]n\in \{0,\dots, p-1\}\setminus A[/tex]. Moreover since G is a group, there exists [tex]g\in G[/tex] such that [tex]g\cdot m=n[/tex] if you think of m and n as elements of G. But this is the same as saying [tex]n\in gA[/tex], 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.

About Vadim Kulikov

For details see this
This entry was posted in Algebra, Combinatorics, Mathematics and tagged . Bookmark the permalink.

5 Responses to Using Abstract Algebra To Understand Basic Combinatorics

  1. janka says:

    Why p divides all the numbers in one line in Pascal triangle?
    I would look at the expression of (p over k) as the ratio of three factorial expressions. Obviously, p divides the numerator p!. In the denominator there is a product of k! and (p-k)! and none of the factors nor their product is divisible by p because they are produced from small numbers (< p) and p is prime.

  2. janka says:

    In the “divisibiity proof” you do not need to know what a group action is :-)
    As for me, to prove that (p over k) = p!/k!(p-k)! is not harder
    than to explain what a group action is.

  3. janka says:

    but of course, you may like the algebraic proof.
    There’s no accounting for taste.

Leave a Reply

Your email address will not be published.