Counting the size of sets of permutations having k cycles

Question

I'm trying to teach myself combinatorics from Bender and Williamson's Foundations of Combinatorics with Applications (2006). Without an instructor to assist I am at times stymied by the perceived terseness. The following contains excerpts from the chapter section on Burnside's Lemma.

Background: The first part of the chapter section discusses permutation functions g ∈ G. Burnside's Lemma is then introduced. I begin to get a bit lost, however, when the gamma function is introduced:

Instead of looking at permutations...we can look at the way the permutation rearranges the positions of the sequence. For example g₂(x₁x₂x₃x₄x₅x₆) = x₃x₄x₅x₆x₁x₂ can be interpreted as saying position 1 is replaced by position 3, position 2 is replaced by position 4, and so forth... To emphasize both the difference and the relationship, we use γ... In cycle form γ₂ = (1,3,5)(2,4,6).

The gamma function is then spelled out a bit more formally.

Principle: In the set of allowed functions, N(γ) counts precisely those allowed functions which are constant on the cycles of γ; i.e. those functions f such that f(x) = f(y) whenever x and y are in the same cycle γ.

Here comes the actual problem:

How many ways can 4 identical round green beads and 4 identical round red beads be arranged to form a necklace of 8 beads?... Obviously all that matters for counting purposes is the size of the cycles--not what they contain. Altogether there are 16 permutations of 8, which are shown here in 5 classes, where P_k is the set of permutations having k cycles...

P₈ (1)(2)(3)(4)(5)(6)(7)(8)

P₅ (1)(2,8)(3,7)(4,6)(5), (1,3)(2)(4,8)(5,7)(6), (1,5)(2,4)(3)(6,8)(7), (1,7)(2,6)(3,5)(4)(8)

P₄ (1,5)(2,6)(3,7)(4,8), (1,2)(3,8)(4,7)(5,6), (1,4)(2,3)(5,8)(6,7), (1,6)(2,5)(3,4)(7,8), (1,8)(2,7)(3,6)(4,5)

P₂ (1,3,5,7)(2,4,6,8), (1,7,5,3)(2,8,6,4)

P₁ (1,2,3,4,5,6,7,8), (1,4,7,2,5,8,3,6), (1,8,7,6,5,4,3,2), (1,6,3,8,5,2,7,4)

My Questions:

1. I don't immediately see how one gets 16 permutations on the set {1,2,...,8}. Is there a way to count the size of and/or enumerate the elements in each P_k other than tedious inspection?

2. Remind me, what exactly is the difference between permutation (1)(2)(3)(4)(5)(6)(7)(8) and permutation (1,2,3,4,5,6,7,8)?

3. Why are there no P₃, P₆, or P₇? Why can't (1,3,5)(2,4,6)(7,8) be a permutation? Is there a way to determine that other than inspection?

4. What precisely does it mean for a function to "be constant on the cycles of γ"?

If I take the above for granted I can mostly follow the rest of the argument. To be clear, this is not homework, so I would really appreciate as much detail as possible. Yes, I have read and done many of the problems in previous chapters, but I'm stumbling on this point nonetheless. Reviewing other bread-counting questions has so far not proved too helpful.

Thank you for any clarification.

[Note: Apologies for some of formatting. Not sure why it won't allow me to have whitespace in a comma-delimited list]

Answer 1

I read the chapter, here's my take on it. Recall the setup, we consider strings of length 8, composed of four 0's and four 1's, for example 00001111 or 01101001, which is the set $\{0,1\}^8$. Now, we consider equivalence classes on these strings to obtain the necklaces.

1. The eight strings $00001111, 10000111,11000011,11100001,\dots,00111100,00011110$ all represent the same necklace, we only start to read at different positions. But at each of these eight positions we may also read from right to left, that's the flipping part. So, in total we get $8\cdot 2=16$ permutations. I don't know any better way to obtain the number of elements in $P_k$.
2. The cyclic permutations can be understood as a shorthand notation. To understand $\gamma=(146)(253)$, you can start by writing down $$\begin{pmatrix}1 & 2& 3& 4&5&6\\\,\end{pmatrix},$$ so just the integers appearing in $\gamma$ (no matter where) in increasing order in the first row, leaving the second row blank. Next, we look at the first cycle $(146)$. This means that we map $1$ to $4$, which we map to $6$, which we map to $1$ (since it is a cycle). In the matrix this amounts to $$\begin{pmatrix}1 & 2& 3& 4&5&6\\4&&&6&&1\end{pmatrix}.$$ The second cycle $(253)$ means that we map $2$ to $5$ to $3$ to $2$, yielding $$\begin{pmatrix}1 & 2& 3& 4&5&6\\4&5&2&6&3&1\end{pmatrix}.$$ This matrix written as a map $g$ would be $g(1)=4$, $g(2)=5$, $g(3)=2$, $g(4)=6$, $g(5)=3$, $g(6)=1$. Applying this to $(1)(2)(3)(4)(5)(6)(7)(8)$ gives $1$ to $1$, $2$ to $2$,...,$8$ to $8$ (we only close the cycles), which is the identity. On the other hand, the cycle $(1 2 3 4 5 6 7 8)$ gives $1$ to $2$, $2$ to $3$, $3$ to $4$,...,$7$ to $8$, $8$ to $1$, which is $$\begin{pmatrix}1 & 2& 3& 4&5&6&7&8\\2&3&4&5&6&7&8&1\end{pmatrix}.$$
3. We will have to write the $16$ permutations down, and then translate them into cyclic permutations. The shifts are \begin{align*} g_0&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 1&2&3&4&5&6&7&8 \end{pmatrix},\\ g_1&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 2&3&4&5&6&7&8&1 \end{pmatrix},\\ g_2&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 3&4&5&6&7&8&1&2 \end{pmatrix},\\ g_3&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 4&5&6&7&8&1&2&3 \end{pmatrix},\\ g_4&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 5&6&7&8&1&2&3&4 \end{pmatrix},\\ g_5&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 6&7&8&1&2&3&4&5 \end{pmatrix},\\ g_6&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 7&8&1&2&3&4&5&6 \end{pmatrix},\\ g_7&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 8&1&2&3&4&5&6&7 \end{pmatrix}. \end{align*} The shifts with negative orientation are \begin{align*} g_{-0}&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 1&8&7&6&5&4&3&2 \end{pmatrix},\\ g_{-1}&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 2&1&8&7&6&5&4&3 \end{pmatrix},\\ g_{-2}&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 3&2&1&8&7&6&5&4 \end{pmatrix},\\ g_{-3}&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 4&3&2&1&8&7&6&5 \end{pmatrix},\\ g_{-4}&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 5&4&3&2&1&8&7&6 \end{pmatrix},\\ g_{-5}&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 6&5&4&3&2&1&8&7 \end{pmatrix},\\ g_{-6}&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 7&6&5&4&3&2&1&8 \end{pmatrix},\\ g_{-7}&=\begin{pmatrix} 1&2&3&4&5&6&7&8\\ 8&7&6&5&4&3&2&1 \end{pmatrix}. \end{align*} This yields the cyclic permutations. We denote the number of cycles with $k$, to indicate which $P_k$ the cyclic permutation belongs to: \begin{align*} \gamma_0&=(1)(2)(3)(4)(5)(6)(7)(8),k=8,\\ \gamma_1&=(12345678),k=1,\\ \gamma_2&=(1357)(2468),k=2,\\ \gamma_3&=(14725836),k=1,\\ \gamma_4&=(15)(26)(37)(48),k=4,\\ \gamma_5&=(16385274),k=1,\\ \gamma_6&=(1753)(2864),k=2,\\ \gamma_7&=(18765432),k=1,\\ \gamma_{-0}&=(1)(28)(37)(46)(5),k=5,\\ \gamma_{-1}&=(12)(38)(47)(56),k=4,\\ \gamma_{-2}&=(13)(2)(48)(57)(6),k=5,\\ \gamma_{-3}&=(14)(23)(58)(67),k=4,\\ \gamma_{-4}&=(15)(24)(3)(68)(7),k=5,\\ \gamma_{-5}&=(16)(25)(34)(78),k=4,\\ \gamma_{-6}&=(17)(26)(35)(4)(8),k=5,\\ \gamma_{-7}&=(18)(27)(36)(45),k=4. \end{align*} Now, it should be clear why $P_3$, $P_6$, $P_7$ are missing.
4. A function $f:\{1,\dots,6\}\rightarrow\{0,1\}$ is constant on the cycles of $\gamma=(146)(253)$ if $f(1)=f(4)=f(6)$ and $f(2)=f(5)=f(3)$. Let $g$ be the permutation corresponding to $\gamma$, as in Item 2. Notice that we have $f\circ g=f$, where $(f\circ g)(x)=f(g(x))$ is the composition. In the example with the necklaces we have to pay attention since we need to have exactly $4$ zeros and $4$ ones. So, we have $N(g_0)=\binom{8}{4}$ since we can choose $4$ position for the zeros to obtain a function $f$ (which doesn't have to be constant anywhere because all cycles have length $1$). A more interesting example is $N(\gamma_{-2})=\binom{3}{2}+\binom{3}{1}\binom{2}{2}=6$, where we can either choose two out of the three cycles of length two (yielding four positions in total) to equip with the zeros, or we choose one out of three cycles of length two and both cycles of length one (four positions in total) for the zeros. The remainder follows analogously.

Equivalences: Here's a picture to illustrate the 16 permutations. The upper half shows a possible necklace, then we flip it upside down, displayed in the lower half, still the same necklace. Both in the upper half and in the lower half we obtain the string from the necklace by choosing a starting point and writing down the eight colors. Each of the resulting strings represents this same necklace, as explained under Item 1.

$\hspace{5cm}$

Equivalence Classes: For completeness, here are all $8$ possible necklaces. Mathematically, these are equivalence classes, that is, sets of strings that result in the same necklace. Notice that in the sets below, I have listed some elements multiple times. The reason is that the sets are all constructed in the same manner, by applying the permutations $g_0,g_7,\dots,g_1,g_{-0},g_{-7},\dots,g_{-1}$, which explains why, there are listed $16$ elements in each set (counting each ocurence of each element). Say, we consider the equivalence class $[00101011]$. The string $00101011$ corresponds to a function $f(1)=0$, $f(2)=0$, $f(3)=1$, $f(4)=0$, $f(5)=1$, $f(6)=0$, $f(7)=1$, $f(8)=1$. The set is constructed as follows. First, we take $f\circ g_0$, meaning $(f\circ g_0)(1)=f(g_0(1))=f(1)$, $(f\circ g_0)(2)=f(g_0(2))=f(2)$,...,$(f\circ g_0)(8)=f(g_0(8))=f(8)$, so $f\circ g_0=f$, which corresponds to the same string, the first element in the set. The second element is obtained from $f\circ g_7$, that is $(f\circ g_7)(1)=f(g_7(1))=f(8)=1$, $(f\circ g_7)(2)=f(g_7(2))=f(1)=0$, $(f\circ g_7)(3)=f(g_7(3))=f(2)=0$, $(f\circ g_7)(4)=f(g_7(4))=f(3)=1$, $(f\circ g_7)(5)=f(g_7(5))=f(4)=0$, $(f\circ g_7)(6)=f(g_7(6))=f(5)=1$, $(f\circ g_7)(7)=f(g_7(7))=f(6)=0$, $(f\circ g_7)(8)=f(g_7(8))=f(7)=1$, so the element is $10010101$. The other elements are computed analogously. If you remove all duplicate entries in the sets, then you will get $8$ equivalence classes, which are the sets and represent the necklaces, with a total of $70$ elements, which are the strings. \begin{align*} [00001111]&=\{00001111,10000111,11000011,11100001,11110000,01111000,00111100,00011110,\\ &\phantom{=\{}01111000,11110000,11100001,11000011,10000111,00001111,00011110,00111100\},\\ [00010111]&=\{00010111,10001011,11000101,11100010,01110001,10111000,01011100,00101110,\\ &\phantom{=\{} 01110100,11101000,11010001,10100011,01000111,10001110,00011101,00111010\},\\ [00011011]&=\{ 00011011,10001101,11000110,01100011,10110001,11011000,01101100,00110110,\\ &\phantom{=\{} 01101100,11011000,10110001,01100011,11000110,10001101,00011011,00110110\},\\ [00011101]&=[00010111],\\ [00011110]&=[00001111]\quad\textrm{(I will skip duplicates now)},\\ [00100111]&=\{ 00100111,10010011,11001001,11100100,01110010,00111001,10011100,01001110,\\ &\phantom{=\{} 01110010,11100100,11001001,10010011,00100111,01001110,10011100,00111001\},\\ [00101011]&=\{ 00101011,10010101,11001010,01100101,10110010,01011001,10101100,01010110,\\ &\phantom{=\{} 01101010,11010100,10101001,01010011,10100110,01001101,10011010,00110101\},\\ [00101101]&=\{ 00101101,10010110,01001011,10100101,11010010,01101001,10110100,01011010,\\ &\phantom{=\{} 01011010,10110100,01101001,11010010,10100101,01001011,10010110,00101101\},\\ [00110011]&=\{ 00110011,10011001,11001100,01100110,00110011,10011001,11001100,01100110,\\ &\phantom{=\{} 01100110,11001100,10011001,00110011,01100110,11001100,10011001,00110011\},\\ [01010101]&=\{ 01010101,10101010,01010101,10101010,01010101,10101010,01010101,10101010,\\ &\phantom{=\{} 01010101,10101010,01010101,10101010,01010101,10101010,01010101,10101010\},\\ \end{align*}