While tutoring today a student asked me about the following identity
One way to prove it is to count the number of possible triples of sets with . This can be done in two ways. First, if contain elements respectively then the number of such triples clearly equals the left-hand side of . On the other hand, since each element of must belong to one of the four disjoint regions in the picture below
the number of such triples equals precisely .
An algebraic proof can be obtained by repeated use of the binomial theorem:
Similarly, one obtains the more general identity
This also follows from the multinomial theorem since the left-hand side equals
I and some friends just came up with this. (We came up with some ideas for the proof, after coming across the formula on the internet.) This is the coolest application of the Möbius inversion formula that I’ve seen so far.
Let be a prime power and any positive integer. We wish to count the number of monic irreducible polynomials of degree over the finite field .
Note that the zeros of
are precisely the elements of degree over , where the product is taken over monic irreducible polynomials . Further, we have the following:
Lemma 1. Let be relatively prime polynomials over a field . Then and have no common zeros.
Proof. Since is a PID, there are polynomials such that . If is a common zero of and in some extension , then divides in , a contradiction.
Lemma 2. If is irreducible over a field , then has distinct zeros.
Proof. Note that any multiple zero of must be a common zero of and its formal derivative . Since is irreducible over , it follows that and are relatively prime over . Now apply lemma 1 to and .
It follows that the zeros of
are all distinct and are precisely the elements of the union of all the subfields of , which is just . This implies
since is the splitting field of over . Now a comparison of the degrees of both sides reveals that
Finally, Möbius inversion gives
Let be Euler’s function, i.e., the number of positive integers not exceeding that are coprime to . A famous identity goes as follows:
where the sum is taken over all positive divisors of . Here is a counting argument for a proof.
Let . For each divisor of , let us count the number of elements with . When , this is just . What about when ? If is odd then clearly there is no such . Otherwise, implies that and must both be even. Moreover, this happens iff . Hence, as before, the number of such is .
This works in general: for any , the number of elements such that is . So summing over all , which is the same as summing over all , gives the total number of elements of , which is . This proves the desired result.
This begs for a generalisation. I will add it here when I come up with one. (I really need to sleep now!)
Let be an element of order 2. Then must be a product of disjoint transpositions. Hence can be chosen in
ways. So there are exactly
elements of order 2 in .
This can also be expressed in terms of the double factorial
The following table lists several values of (left column) along with the number of elements of order 2 in :
An interesting feature of the table is that the entries on the second column, except for the first row, are all odd. This is true in general and is not difficult to prove. Using the double factorial notation, the number of elements of order 2 is
Using the binomial theorem for and one deduces
as expected. Thus
Fact. The number of elements of order 2 in is odd for every .