Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Burnside's lemma
Summary
Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy–Frobenius lemma, the orbit-counting theorem, or the lemma that is not Burnside's, is a result in group theory that is often useful in taking account of symmetry when counting mathematical objects. Its various eponyms are based on William Burnside, George Pólya, Augustin Louis Cauchy, and Ferdinand Georg Frobenius. The result is not due to Burnside himself, who merely quotes it in his book 'On the Theory of Groups of Finite Order', attributing it instead to . Burnside's Lemma counts "orbits", which is the same thing as counting distinct objects taking account of a symmetry. Other ways of saying it are counting distinct objects up to an equivalence relation R, or counting objects that are in canonical form.
In the following, let G be a finite group that acts on a set X. For each g in G, let Xg denote the set of elements in X that are fixed by g (also said to be left invariant by g), that is, Xg = { x ∈ X | g.x = x }. Burnside's lemma asserts the following formula for the number of orbits, denoted |X/G|:
Thus the number of orbits (a natural number or +∞) is equal to the average number of points fixed by an element of G (which is also a natural number or infinity). If G is infinite, the division by |G| may not be well-defined; in this case the following statement in cardinal arithmetic holds:
There are 8 possible bit vectors of length 3, but only four distinct 2-colored necklaces of length 3 (000, 001, 011, and 111), because 100 and 010 are equivalent to 001 by rotation, and similarly 110 and 101 are equivalent to 011. The formula is based on the number of rotations, which in this case is 3 (including the null rotation), and the number of bit vectors left unchanged by each rotation. All 8 bit vectors are unchanged by the null rotation, and two (000 and 111) are unchanged by each of the other two rotations.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.