Pólya's Enumeration Theorem: exercises

Practice (11)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. Write the permutations shown below in cycle notation. \[\begin{aligned}\pi_1 \amp = \begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \\ 4 \amp 2 \amp 5 \amp 6 \amp 3 \amp 1 \end{pmatrix} \amp \pi_2 \amp = \begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \\ 5 \amp 6 \amp 1 \amp 3 \amp 4 \amp 2 \end{pmatrix} \\ \pi_3 \amp = \begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \amp 8 \\ 3 \amp 1 \amp 5 \amp 8 \amp 2 \amp 6 \amp 4 \amp 7 \end{pmatrix} \amp \pi_4 \amp = \begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \amp 8 \\ 3 \amp 7 \amp 1 \amp 6 \amp 8 \amp 4 \amp 2 \amp 5 \end{pmatrix}\end{aligned}\]

2. Compute \(\pi_1\pi_2\), \(\pi_2\pi_1\), \(\pi_3\pi_4\), and \(\pi_4\pi_3\) for the permutations \(\pi_i\) in .

3. Find \(\stab_{D_8}(C_3)\) and \(\stab_{D_8}(C_{16})\) for the colorings of the vertices of the square shown in by referring to .

4. In , we show a regular pentagon with its vertices labeled. Use this labeling to complete this exercise.

   1. The dihedral group of the pentagon, \(D_{10}\), contains \(10\) permutations. Let \(r_1=(12345)\) be the clockwise rotation by \(72^\circ\) and \(f_1=(1)(25)(34)\) be the flip about the line passing through \(1\) and perpendicular to the opposite side. Let \(r_2\), \(r_3\), and \(r_4\) be the other rotations in \(D_{10}\). Denote the flip about the line passing through vertex \(i\) and perpendicular to the other side by \(f_i\), \(1\leq i\leq 5\). Write all \(10\) elements of \(D_{10}\) in cycle notation.

   2. Suppose we are coloring the vertices of the pentagon using black and white. Draw the colorings fixed by \(r_1\). Draw the colorings fixed by \(f_1\).

   3. Find \(\stab_{D_{10}}(C)\) where \(C\) is the coloring of the vertices of the pentagon in which vertices \(1\), \(2\), and \(5\) are colored black and vertices \(3\) and \(4\) are colored white.

   4. Find the cycle index of \(D_{10}\).

   5. Use the cycle index to determine the number of nonequivalent colorings of vertices of the pentagon using black and white.

   6. Making an appropriate substitution for the \(x_i\) in the cycle index, find the number of nonequivalent colorings of the vertices of the pentagon in which two vertices are colored black and three vertices are colored white. Draw these colorings.

5. Write all permutations in \(C_{12}\), the cyclic group of order \(12\), in cycle notation.

6. The \(12\)-note western scale is not the only system on which music is based. In classical Thai music, a scale with seven equally-spaced notes per octave is used. As in western music, a scale is a subset of these seven notes, and two scales are equivalent if they are transpositions of each other. Find the number of \(k\)-note scales in classical Thai music for \(1\leq k\leq 7\).

7. Xylene is an aromatic hydrocarbon having two methyl groups (and four hydrogen atoms) attached to the hexagonal carbon ring. How many isomers are there of xylene?

8. Find the permutations in \(S_4^{(2)}\) corresponding to the permutations \((1234)\) and \((12)(34)\) in \(S_4\). Confirm that the first consists of a \(4\)-cycle and a \(2\)-cycle and the second consists of two \(2\)-cycles and two \(1\)-cycles.

9. Draw the three nonisomorphic graphs on four vertices with \(3\) edges and the two nonisomorphic graphs on four vertices with \(4\) edges.

10. 1. Use the method of to find the cycle index of the pair group \(S_5^{(2)}\) of the symmetric group on five elements.

    2. Use the cycle index from to determine the number of nonisomorphic graphs on five vertices. How many of them have \(6\) edges?

11. Suppose you are painting the faces of a cube and you have white, gold, and blue paint available. Two painted cubes are equivalent if you can rotate one of them so that all corresponding faces are painted the same color. Determine the number of nonequivalent ways you can paint the faces of the cube as well as the number having two faces of each color.

    Cevabı açıkla.

    Hint:

    It may be helpful to label the faces as \(U\) (up), \(D\) (down), \(F\) (front), \(B\) (back), \(L\) (left), and \(R\) (right) instead of using integers. Working with a three-dimensional model of a cube will also aid in identifying the permutations you require.

Symbols used here

\pi

pi
Ratio of a circle's circumference to its diameter, 3.14159…

A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}

matrix
A rectangular array of numbers; a linear map.

i

imaginary unit
i² = −1.

^\circ

degrees
1/360 of a full turn. 180° = π radians.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

n!

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Kendini dene.

⌨ Type ✎ Draw

Matematik sorunun.

Çöz

x²√÷×π( )=∫d/dxlim[ ]sinlogeˣ

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Daha fazlası Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs