Symmetry and counting · Definition

Burnside's lemma

enumerative combinatoricssymmetry and counting

Before you start you need to know

When a group acts on a set, many configurations are equivalent to each other. This lemma lets you count the equivalence classes without listing them one by one.

Definition

Burnside's lemma (also called the Cauchy-Frobenius lemma) states that the number of orbits of a finite group G acting on a set X equals the average number of fixed points of the elements of G.

\[|X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|\]

Let G be a finite group acting on X. By the orbit-stabilizer theorem, \(|G| = |G_x|\cdot|Gx|\) for each x, which leads to counting pairs (g,x) with gx = x in two different ways. The result is \(\sum_{g}|X^g| = \sum_{x}|G_x| = |G|\cdot|X/G|\), which is the formula of the lemma.

Guide example: coloring the faces of a square with two colors using the rotations of \(C_4\) (identity, 90°, 180° and 270° turns), the identity fixes 16 colorings, the 90° and 270° turns each fix 2, and the 180° turn fixes 4. Thus the number of distinct colorings is \((16+2+4+2)/4 = 6\).

Typical error: forgetting to include the identity in the sum, which always fixes every element of X. Omitting it lowers the sum and, in the example above, would give \((2+4+2)/4 = 2\) instead of 6.

Think about it

Why is the sum of fixed points always a multiple of \(|G|\)?

Because \(\sum_{g}|X^g| = |G|\cdot|X/G|\) and the number of orbits \(|X/G|\) is an integer.

Exercises 10

  1. According to Burnside's lemma, what does the expression \(\frac{1}{|G|}\sum_{g}|X^g|\) count?
  2. How many elements does the rotation group of the square, \(C_4\), have?
  3. Which element of the group always fixes every point of X?
  4. If \(|G| = 6\) and the sum of fixed points is 18, how many orbits are there?
  5. What alternative name does Burnside's lemma receive?
  6. A group of order 4 acts on a set of 10 elements. Its fixed-point counts sum to \(4+2+2+0\). How many orbits are there?
  7. How many distinct colorings are there when coloring a square with 3 colors, using only rotations (group \(C_4\) with identity, 90°, 180° and 270°)?
  8. A group of order 3 acts on a set of 7 elements with fixed-point counts 7, 1 and 1. How many orbits are there?
  9. How many distinct necklaces of 4 beads with 2 colors are there, if rotations of \(C_4\) are allowed?
  10. A group of 6 elements acts on a set X. The sum of the fixed points of all its elements, \(\sum_{g}|X^g|\), is 20. What can be concluded?

References

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.