Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Counting > Burnside's lemma

Burnside's lemma, is also called Burnside's counting theorem, the Cauchy-Frobenius lemma or the orbit-counting theorem.

Burnside's Lemma

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.  Burnside's lemma asserts the following formula for the number of orbits, denoted |X/G|:

|X/G| = 

 1 
|G|

 

 g

|Xg|

Two elements of X belong to the same "orbit" when one can be reached from the other by through the action of an element of G.  For example, if X is the set of colorings of a cube, and G is the set of rotations of the cube, then two elements of X belong to the same orbit precisely when one is a rotation of the other.

Example

6 people are to select a piece each from 10 pieces of cake, of which there are 2 pieces each of 5 different kinds.  How many ways is this possible?

Solution:

Create 4 more virtual people.  Now there are 10 pieces of cake to be distributed among 10 people.  The number of permutations of 10 things is 10!, and since there are 5 indistinguishable pairs, we divide by 2^5.  10!/2^5=113400 is the number of elements of X.

Now we apply Burnside's lemma, where the permutation group of order 113400 is acted on by the group of permutations of the four virtual people, of size 4! = 24.  That is, if two of the 113400 elements of X can be reached by permuting the four virtual people, then they belong to the same orbit, and so the number of orbits is the number of distinct answers to the original question.

The group of permutations of 4 objects has 1 identity element, six 2-cycles, eight 3-cycles, six 4-cycles, and 3 pairs of 2-cycles, as given by the following table:

cycles number of permutations example
identity 1 (1)(2)(3)(4)
2-cycles 6 (12)(3)(4)
3-cycles 8 (123)(4)
4-cycles 6 (1234)
pair of 2-cycles 3 (12)(34)
Total 24  

Next, we find the number of elements of X that are fixed under each permutation of G, and add them up.  That means, for a given permutation of G, for example interchanging the cakes selected by virtual persons 1 and 2, what elements of X are left unchanged?  That would be just the elements of X in which virtual persons 1 and 2 have the same kind of cake.  The number of such elements is the number of ways for persons 1 and 2 to pick one kind of cake, and then persons 3 through 10 to choose from two pieces of each of four kinds of cake -- the example is filled out as the second row of the following table:

cycles number of permutations example Fixed elements of X under this permutation (# perm)*(fixed elements in this perm) = total fixed elements of X
identity 1 (1)(2)(3)(4) All of them: 10!/25=113400 1 * 113400 = 113,400
2-cycles 6 (12)(3)(4) Elements of X are fixed if 1 and 2 have the same type of cake.  5 ways to pick a type of cake for 1,2 to share, then 8!/24 ways to pick the other pieces.  5*8!/24=12600. 6 * 12600 = 75,600
3-cycles 8 (123)(4) None of the elements of X are fixed by a 3-cycle, because 1,2,3 must have at least two kinds of cake among them. 0
4-cycles 6 (1234) No fixed elements of X. 0
pair of 2-cycles 3 (12)(34) 5 ways to pick the kind of cake for 1,2; 4 ways to pick the kind of cake for 3,4; 6!/23 ways to pick the other pieces.  5*4*6!/23=1800. 3 * 1800 = 5400
Total 24     194,400

Finally, 194400/24 = 8100, which is the number of orbits of X under permutations of the virtual people.

 

Same example not using Burnside's Lemma -- the hard way (cases)

To illustrate how hard this problem is without Burnside's Lemma, I'll show you how I solved it before this wonderful lemma was pointed out to me...

Proof that 6 distinct people (123456) can choose a piece of cake from 2 of each of 5 kinds (AABBCCDDEE) in 8100 ways:

For each of the 5 cases where person 1 and person 2 choose the same kind of cake, then persons 3-6 have 204 ways to choose among the remaining 4 kinds of cake.

For each of the 20 cases where person 1 and person 2 chose different kinds of cake, then persons 3-6 have 354 ways to choose among the remaining eight pieces of cake.

5*204 + 20*354 = 8100

Proof that 4 distinct people (3456) can choose a piece of cake from 2 of each of 4 kinds (BBCCDDEE) in 204 ways:

For each of the 4 cases where person 3 and person 4 choose the same kind of cake, then persons 5-6 have 9 ways to pick cake from CCDDEE, namely CC, CD, CE, DC, DD, DE, EC, ED, EE.

For each of the 12 cases where persons 3 and 4 choose different kinds of cake, then persons 5-6 have 14 ways to pick cake from BCDDEE, namely BC, BD, BE, CB, CD, CE, DB, DC, DD, DE, EB, EC, ED, EE.

4*9 + 12*14 = 204

Proof that 4 distinct people (3456) can choose a piece of cake from (ABCCDDEE) in 354 ways:

For the 2 cases where persons 3 and 4 choose A and B, then persons 5-6 have 9 ways to pick cake from CCDDEE (see above).

For the 12 cases where person 3 or 4 chooses A or B, and person 4 or 3, respectively, chooses C, D, or E, then persons 5-6 have 14 ways to pick from BCDDEE (see above).

For the 6 cases where persons 3 and 4 each choose different C, D, or E, then persons 5-6 have 21 ways to pick from ABCDEE, namely AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC, ED, EE

For the 3 cases where persons 3 and 4 each choose CC, DD, or EE, then persons 5-6 have 14 ways to pick from ABEE, namely AB, AD, AE, BA, BD, BE, DA, DB, DD, DE, EA, EB, ED, EE

2*9 + 12*14 + 6*21 + 3*14 = 354

Same example not using Burnside's Lemma -- the easy way

This puzzle can be divided into three cases:

Case 1: Only two people choose the same kind of cake as another person.

In this case, there are C(5,1)=5 ways to choose the kind of cake chosen by 2 people, and then 6!/2 ways to permute the cakes, considering that one pair of cakes are indistinguishable.  5*6!/2=1800.

Case 2: Four of the people choose the same kind of cake as another person.

In this case, there are C(5,2)=10 ways to choose the two kinds of cake chosen by these 4 people, and C(3,2) ways for the two remaining people to choose from among the three other cake types.  Then there are 6!/4 ways to permute the cakes, considering two pairs of cakes are indistinguishable.  10*3*6!/4=5400.

Case 3: All six people choose the same kind of cake as another person.

In this case, there are C(5,3)=10 ways to choose the three kinds of cake, and then 6!/8 ways to permute the cakes, considering three pairs of cakes are indistinguishable.  10*6!/8=900.

Adding the cases, 1800+5400+900=8100.

Internet references

Wikipedia: Burnside's lemma -- example of the 57 colorings of the faces of a cube with three colors.

Mathworld: Cauchy-Frobenius Lemma

Dr. Math: Permutations in a Necklace -- using Burnside's Lemma to count the number of different necklaces. (From the same site: Polya-Burnside Lemma)

Jaap's Puzzle Page: Useful Mathematics -- Permutations, The parity of a permutation, Disjoint cycle notation, The Order of a permutation, Groups, Conjugation, Commutation Size of the group, Subgroups, Centre, Supergroup, Metrics, God's Algorithm, Counting, The number of orientations, The number of permutations, The number of combinations, Burnside's Lemma

Bard College Abstract Algebra Math332: Quiz2 Practice Problems.pdf (mirror)

Haskell for Maths: Polya Counting -- How many different ways are there to colour the faces of a dodecahedron using red, green and blue? No, the answer's not 312...

Related pages in this website

"hyper-binary" partition

Combination identities


The webmaster and author of this Math Help site is Graeme McRae.