Start typing to search every page on this site.

Use ↑ and ↓ to move through results, then Enter to open one.

    Skip to main content

    Midterm 3 Practice Worksheet 4: Burnside’s Lemma#

    This worksheet is optional practice for Midterm 3. It is not collected or graded. Work on paper, as you would on the exam, and write the method that justifies each answer. Then compare with the solutions.

    This worksheet covers counting colorings up to symmetry with Burnside’s lemma: for colorings with colors, where counts the cycles of on the positions, including fixed positions. For each count, organize the computation in a table: kind of element, how many, , fixed colorings, and their product. Check that the result is a whole number.

    1. (Colorings of a flag)#

    A flag is a rectangle divided into rows and columns of square cells, numbered as in the figure.

    A rectangle of square cells in 3 rows and 4 columns, numbered 1 to 4 in the top row, 5 to 8 in the middle row, and 9 to 12 in the bottom row, from left to right. A dashed horizontal line labeled a runs through the middle row, and a dashed vertical line labeled b runs between the second and the third column.
    Figure 1: The cells of the flag, with the mirror lines of the reflections and .#

    The rectangle has four symmetries, which form a group : the identity ; the half turn about the center of the rectangle; the reflection across the horizontal line through the middle row; and the reflection across the vertical line between the second and the third column. Each cell is colored with one of colors, and two colorings are the same up to symmetry if some element of carries one to the other.

    1. (A) Write , , and as permutations of the cells in cycle notation. For each of the four elements , give its cycle type and .

    2. (B) For each , find . For , explain which cells must have the same color in a coloring fixed by .

    3. (C) Use Burnside’s lemma to find the number of colorings up to symmetry.

    4. (D) Find a formula, in terms of , for the number of colorings with colors up to symmetry. Check that it gives for .

    2. (Colorings of a longer flag)#

    A second flag is a rectangle divided into rows and columns of square cells, numbered as in the figure.

    A rectangle of square cells in 2 rows and 5 columns. The top row has cells 1 to 5 and the bottom row has cells 6 to 10, from left to right.
    Figure 2: The cells of the flag.#

    The rectangle has four symmetries, which form a group : the identity ; the half turn about the center of the rectangle; the reflection across the horizontal line between the two rows; and the reflection across the vertical line through the middle column. Each cell is colored with one of colors, and two colorings are the same up to symmetry if some element of carries one to the other.

    1. (A) Write , , and as permutations of the cells in cycle notation. For each of the four elements , give its cycle type and .

    2. (B) For each , find the number of colorings fixed by . For , explain which cells must have the same color in a coloring fixed by .

    3. (C) Use Burnside’s lemma to find the number of colorings up to symmetry.

    3. (Necklaces and bracelets)#

    Beads of colors are placed at the corners of a regular pentagon. Number the corners counterclockwise, starting at the bottom, as in the figure.

    A regular pentagon with corner 1 at the bottom and the other corners counterclockwise: 2 at the lower right, 3 at the upper right, 4 at the upper left, and 5 at the lower left. A dashed vertical mirror line labeled s passes through corner 1 and the center, and a counterclockwise arrow labeled r turns about the center.
    Figure 3: The labeled pentagon, the rotation , and the mirror line of .#

    1. (A) Two colorings are the same necklace if a rotation carries one to the other. For each of the rotations, find and the number of colorings it fixes. How many necklaces are there?

    2. (B) Two colorings are the same bracelet if a rotation or a reflection carries one to the other. Find of each reflection, and count the bracelets.

    3. (C) Explain why there cannot be more bracelets than necklaces.

    4. (Colorings of a square grid)#

    The cells of a grid are numbered as in the figure and colored with colors.

    A 2 by 2 grid with cells 1 and 2 in the top row and cells 3 and 4 in the bottom row, from left to right.
    Figure 4: The cells of the grid.#

    1. (A) Write the four rotations of the grid as permutations of the cells, and count the colorings up to rotation.

    2. (B) Write the four reflections of the grid as permutations of the cells (across the vertical and horizontal midlines, and across the two diagonals), and count the colorings up to rotations and reflections.

    5. (Colorings of solids)#

    Use your tables from Practice Worksheet 3 (or make them now) to count the following colorings up to rotation.

    1. (A) The vertices of a regular tetrahedron, with colors.

    2. (B) The faces of a cube, with colors.

    3. (C) The vertices of a cube, with colors.

    4. (D) The faces of a triangular prism (two equilateral triangles and three squares), with colors.

    Hint#

    Rotations of the same kind have the same number of cycles, so each kind contributes (number of rotations of that kind) times . Make sure that the numbers of rotations add up to the order of the group.

    6. (Strings up to reversal)#

    1. (A) How many strings of length over the alphabet are there, if a string and its reversal count as the same?

    2. (B) How many bit strings of length are there, if a string and its reversal count as the same?

    On this page