第 14 章 Pólya Counting

EX1 🚧

Let

$$f=\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 6& 4& 2& 1& 5& 3\end{array}\right)\text{ and }g=\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 3& 5& 6& 2& 4& 1\end{array}\right).$$

Determine: (a) $f\circ g$ and $g\circ f$ (b) $f^{-1}$ and $g^{-1}$ (c) $f^2$, $g^5$ (d) $f\circ g\circ f$ (e) $g^3$ and $f\circ g^3\circ f^{-1}$

EX2 🚧

Prove that permutation composition is associative: $(f\circ g)\circ h=f\circ (g\circ h)$

EX3 🚧

Determine the symmetry group and corner-symmetry group of an equilateral triangle.

EX4 🚧

Determine the symmetry group and corner-symmetry group of a triangle that is isosceles but not equilateral.

EX5 🚧

Determine the symmetry group and corner-symmetry group of a triangle that is neither equilateral nor isosceles.

EX6 🚧

Determine the symmetry group of a regular tetrahedron. (Hint: There are 12 symmetries.)

EX7 🚧

Determine the corner-symmetry group of a regular tetrahedron.

EX8 🚧

Determine the edge-symmetry group of a regular tetrahedron.

EX9 🚧

Determine the face-symmetry group of a regular tetrahedron.

EX10 🚧

Determine the symmetry group and the corner-symmetry group of a rectangle that is not a square.

EX11 🚧

Compute the corner-symmetry group of a regular hexagon (the dihedral group $D_6$ of order 12).

EX12 🚧

Determine all the permutations in the edge-symmetry group of a square.

EX13 🚧

Let $f$ and $g$ be the permutations in Exercise 1. Consider the coloring $c=(R,B,B,R,R,R)$ of $1,2,3,4,5,6$ with the colors $R$ and $B$. Determine the following actions on $c$: (a) $f\ast c$ (b) $f^{-1}\ast c$ (c) $g\ast c$ (d) $(g\circ f)\ast c$ and $(f\circ g)\ast c$ (e) $(g^2\circ f)\ast c$

EX14 🚧

By examining all possibilities, determine the number of nonequivalent colorings of the corners of an equilateral triangle with the colors red and blue. (Then do so with the colors red, white, and blue.)

EX15 🚧

By examining all possibilities, determine the number of nonequivalent colorings of the corners of a regular tetrahedron with the colors red and blue. (Then do so with the colors red, white, and blue.)

EX16 🚧

Characterize the cycle factorizations of those permutations $f$ in $S_n$ for which $f^{-1}=f$, that is, for which $f^2=\iota$.

EX17 🚧

In Section 14.2 it is stated that there are eight nonequivalent colorings of the corners of a regular pentagon with the colors red and blue. Explicitly determine all eight nonequivalent colorings.

EX18 🚧

Use Theorem 14.2.3 to determine the number of nonequivalent colorings of the corners of a square with $p$ colors.

EX19 🚧

Use Theorem 14.2.3 to determine the number of nonequivalent colorings of the corners of an equilateral triangle with the colors red and blue. Do the same with $p$ colors (cf. Exercise 3).

EX20 🚧

Use Theorem 14.2.3 to determine the number of nonequivalent colorings of the corners of a triangle that is isosceles, but not equilateral, with the colors red and blue. Do the same with $p$ colors (cf. Exercise 4).

EX21 🚧

Use Theorem 14.2.3 to determine the number of nonequivalent colorings of the corners of a triangle that is neither equilateral nor isosceles, with the colors red and blue. Do the same with $p$ colors (cf. Exercise 5).

EX22 🚧

Use Theorem 14.2.3 to determine the number of nonequivalent colorings of the corners of a rectangle that is not a square with the colors red and blue. Do the same with $p$ colors (cf. Exercise 10).

EX23 🚧

A (one-sided) marked domino is a piece consisting of two squares joined along an edge, where each square on one side of the piece is marked with $0,1,2,3,4,5,$ or $6$ dots. The two squares of a marked domino may receive the same number of dots.
(a) Use Theorem 14.2.3 to determine the number of different marked dominoes.
(b) How many different marked dominoes are there if we are allowed to mark the squares with $0,1,2,\dots ,p-1$, or just $0$?

EX24 🚧

A two-sided marked domino is a piece consisting of two squares joined along an edge, where each square on both sides of the piece is marked with $0,1,2,3,4,5,$ or $6$ dots.
(a) Use Theorem 14.2.3 to determine the number of different two-sided marked dominoes.
(b) How many different two-sided marked dominoes are there if we are allowed to mark the squares with $0,1,\dots ,p-1$, or $p$ dots?

EX25 🚧

How many different necklaces are there that contain three red and two blue beads?

EX26 🚧

How many different necklaces are there that contain four red and three blue beads?

EX27 🚧

Determine the cycle factorizations of the permutations $f$ and $g$ in Exercise 1.

EX28 🚧

Let $f$ be a permutation of a set $X$. Give a simple algorithm for finding the cycle factorization of $f^{-1}$ from the cycle factorization of $f$.

EX29 🚧

Determine the cycle factorization of each permutation in the dihedral group $D_6$ (cf. Exercise 11).

EX30 🚧

Determine permutations $f$ and $g$ of the same set $X$ such that $f$ and $g$ each have two cycles in their cycle factorizations but $f\circ g$ has only one.

EX31 🚧

Show that the number of nonequivalent colorings of the corners of a regular 5-gon with $p$ colors is

$$\frac{p(p^2+4)(p^2+1)}{10}.$$

EX32 🚧

Determine the number of nonequivalent colorings of the corners of a regular hexagon with red, white, and blue (cf. Exercise 29).

EX33 🚧

Prove that a permutation and its inverse have the same type (cf. Exercise 28).

EX34 🚧

Let $e_1,e_2,\dots ,e_n$ be nonnegative integers such that $1e_1+2e_2+\cdots +n{e}_n=n$.
Show how to construct a permutation $f$ of the set $\{1,2,\dots ,n\}$ such that the type of $f$ is $(1^{e_1},2^{e_2},\dots ,n^{e_n})$.

EX35 🚧

Determine the number of nonequivalent colorings of the corners of a regular $k$-gon with $k$ colors (cf. Exercise 29).

EX36 🚧

Determine the number of nonequivalent colorings of the corners of a regular 5-gon with red, red, red, white, and blue in which two corners are colored red, two are white, and one is colored blue.

EX37 🚧

Determine the number of nonequivalent colorings of the corners of a regular 8-gon with colors red, white, and blue, and the order of the corner symmetry group of the 8-gon.

EX38 🚧

A two-sided triomino is a $1\times 3$ board of three squares with each square (six in all because of the two sides) colored with one of the colors red, white, blue, green, and yellow (squares on opposite sides may be colored differently). How many nonequivalent two-sided triominoes are there?

EX39 🚧

A two-sided 4-omino is a $1\times 4$ board of four squares with each square (eight in all because of the two sides) colored with one of the colors red, white, blue, green, and yellow (squares on opposite sides may be colored differently). How many nonequivalent two-sided 4-ominoes are there?

EX40 🚧

A two-sided $n$-omino is a $1\times n$ board of $n$ squares with each square ($2n$ in all because of the two sides) colored with one of $p$ given colors (squares on opposite sides may be colored differently). How many nonequivalent two-sided $n$-ominoes are there?

EX41 🚧

Determine the cycle index of the dihedral group $D_6$ (cf. Exercise 29).

EX42 🚧

Determine the generating function for nonequivalent colorings of the corners of a regular hexagon with two colors and also with three colors (cf. Exercise 41).

EX43 🚧

Determine the cycle index of the edge-symmetry group of a square.

EX44 🚧

Determine the generating function for nonequivalent colorings of the edges of a square with $p$ colors, up to edge-flip.
How many nonequivalent colorings are there with 3 colors? (cf. Exercise 43)

EX45 🚧

Let $\pi$ be a permutation of a set. Prove that each of the permutations $f_i$, that send $i$ to $\pi (i)$ for $i\in \{1,2,\dots ,n\}$, is an $n$-cycle. (Recall that $f_i$ is the permutation that sends 1 to $i$, then $\pi (i)$ to ${\pi }^2(i)$, and so on to 1.)

EX46 🚧

Let $p$ be a prime number. Determine the number of different necklaces that can be made with $p$ beads from each of $r$ different colors.

EX47 🚧

There are nine squares of a $3\times 3$ chessboard to be colored red and blue.
The chessboard is fixed to a frame that cannot be flipped over.
Determine the generating function for the number of nonequivalent colorings and the total number of nonequivalent colorings.

EX48 🚧

A stained glass window in the form of a $3\times 3$ chessboard has nine squares, each of which is colored red or blue (the colors are transparent and the window can be looked at from either side).
Determine the generating function for the number of different stained glass windows and the total number of stained glass windows.

EX49 🚧

Repeat Exercise 48 for stained glass windows in the form of a $4\times 4$ chessboard with 16 squares.

EX50 🚧

Find the generating function for the different necklaces that can be made with $p$ beads each of color red or blue if $p$ is a prime number (cf. Exercise 46).

EX51 🚧

Determine the cycle index of the dihedral group $D_{2p}$ where $p$ is a prime number.

EX52 🚧

Find the generating function for the different necklaces that can be made with $2p$ beads each of color red or blue if $p$ is a prime number.

EX53 🚧

Ten balls are stacked in a triangular array with 1 atop 2 atop 3 atop 4. (Think of billiards.) The triangular array is free to rotate. Find the generating function for the number of nonequivalent colorings with two colors, and the corresponding generating function if we are also allowed to turn over the array.

EX54 🚧

Use Theorem 14.3.3 to determine the generating function for nonisomorphic graphs of $n$ vertices. (Hint: This exercise will require some thought and a fitting last exercise. We need to determine the cycle index group $S_n^{(2)}$, where $S_n^{(2)}$ is the action of the symmetric group $S_n$ on the set of 2-element subsets of a graph of $n$ vertices. First, determine the number of permutations of $\{1,2,3,4,5\}$ of each type and show that the type of a 2-set permutation of $X$ depends only on the type of $f$ as a permutation of $\{1,2,3,4,5\}$.)

EX54 🚧

Use Theorem 14.3.3 to determine the generating function for nonisomorphic graphs of order 5. (Hint: This exercise will require some work and is a fitting last exercise. We need to obtain the cycle index of the group $S_5^{(2)}$ of permutations of the set $X$ of 10 unordered pairs of distinct integers from $\{1,2,3,4,5\}$ (the possible edges of a graph of order 5). First, compute the number of permutations $f$ of $S_5$ of each type. Then use the fact that the type of $f$ as a permutation of $X$ depends only on the type of $f$ as a permutation of $\{1,2,3,4,5\}$.)