Nice application of the Cauchy?-Frobenius?-Burnside?-Pólya? formula

Question

Burnside's Lemma, whose list of names is longer than the proof, says that the number of orbits of a permutation group is the average number of fixed points of its elements. It's a very elegant result, but I'm a bit disappointed by the fact that the examples given in the textbooks always amount to counting some colorings of a symmetric object, up to symmetry (the less original example probably being the cube). My question is then: do you know some funnier (but still rather direct) applications of this result?

Answer 1

Burnside's lemma can be used to prove the Polya enumeration theorem, which has many applications; see, for example, these two blog posts. The application to the symmetric groups alone is the well-known exponential formula in combinatorics, which has many applications; see this blog post.

It also has applications to representation theory. If $X$ is a set on which a group $G$ acts, then the free vector space on $X$ is a representation $V$ of $G$ with character $\text{Fix}(g)$. Burnside's lemma and the orthogonality relations then tell you that the dimension of the invariant subspace of $V$ is the number of orbits of the action of $G$ on $X$. They also tell you that if $V$ decomposes as a direct sum $\oplus n_k V_k$ where the $V_k$ are irreducible, then $\sum n_k^2$ is the number of orbits of $G$ acting on $X \times X$. In particular, if $G$ acts double transitively there are two such orbits, so $V$ is the sum of a trivial representation and an irreducible representation.

(This application to representation theory, in turn, has applications to graph theory. See this blog post.)

Edit: Here are some MO and math.SE answers where I have used Burnside's lemma:

• http://mathoverflow.net/questions/50253/can-this-nested-sum-be-expressed-in-terms-of-generalized-harmonic-numbers-and-the/50256#50256
• http://mathoverflow.net/questions/30112/elementary-combinatorial-identity-expressing-binomial-coefficients-as-an-alter/30114#30114
• Coloring the faces of a hypercube

I want to point out one of the applications I mention in one of the above blog posts which I think is particularly "funny": Fermat's little theorem! Consider the cyclic group of order $p$ acting on the set of strings of length $p$ from an alphabet of size $a$. By Burnside's lemma the total number of orbits is

$$\frac{1}{p} \left( a^p + (p-1)a \right)$$

since there is one element which fixes every string and $p-1$ elements which only fix strings which repeat one letter $p$ times. The integrality of this number is equivalent to Fermat's little theorem. (For a generalization, see these two blog posts.)

Answer 2

Yes, there are many more funny applications, for sure, here are three of them:

1. You can apply it in order to compute the sum of reciprocals of cardinals all all endomorphisms of a vector space of dimension $n$ over some field with $p$ elements ($p$ a prime).

2. You can apply it in order to characterize those finite groups that have an abelian automorphism group.

3. It can be applied in order to (pun intended!) calculate the multiplicative order of some $u$ such that $u$ is co-prime to a given $n$ (that is, to calculate the smallest $k$ such that $n$ divides $u^k-1$).

I share with you the disappointment: this is such a general thing that it is only conceivable that the range of applications is bounded only by the imagination of the user...