Manuel Kauers Hagenberg, May 19, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 9

Exercise 1 Apply the Cauchy-Frobenius Lemma in order to determine

|S_{n} \\ \{0, 1\}^{\binom{[n]}{2}}|

for n = 3. (You should obtain the result 4.)

Write G = S_{3} and X = \{0, 1\}^{\binom{[3]}{2}} for short. By the lemma, we have

|G \\ X| = \frac{1}{|G|} ∑_{g∈G} |X_{g}|.

Observe that |G| = 3! = 6. Furthermore, consideration of the number of cycles gives

|X_{(1)(2)(3)}| = 2^{3} = 8,  |X_{(1 2)(3)}| = 2^{2} = 4,
|X_{(1 3)(2)}| = 2^{2} = 4,  |X_{(1)(2 3)}| = 2^{2} = 4,
|X_{(1 2 3)}| = 2^{1} = 2,  |X_{(1 3 2)}| = 2^{1} = 2

and therefore

|G \\ X| = \frac{1}{|G|} ∑_{g∈G} |X_{g}| = \frac{1}{6}(8 + 4 + 4 + 4 + 2 + 2) = 24/6 = 4.

Exercise 2 Apply the Cauchy-Frobenius Lemma in order to determine

|S_{n} \\ \{0, 1\}^{\binom{[n]}{2}}|

for n = 4.

Write G = S_{4} and X = \{0, 1\}^{\binom{[4]}{2}} for short. Consider S_{4} as a subgroup of S_{X}. Using the abreviation

\begin{matrix}a & b & c & d & e & f \\ \{1, 2\} & \{1, 3\} & \{1, 4\} & \{2, 3\} & \{2, 4\} & \{3, 4\} \end{matrix}

we find the following induced permutation representation.

π ∈ S_{4}  π̄ ∈ S_{X}  cn(π̄)
id  id = (a)(b)(c)(d)(e)(f)  6
(1 2 3 4) \begin{cases}a & b & c & d & e & f \\ d & e & a & f & b & c \end{cases}\} = (a d f c)(b e)  2
(1 2 4 3) \begin{cases}a & b & c & d & e & f \\ e & a & d & c & f & b \end{cases}\} = (a e f b)(c d)  2
⋮
(1)(2 3 4) \begin{cases}a & b & c & d & e & f \\ b & c & a & f & d & e \end{cases}\} = (a b c)(d e f)  2
⋮
(1 2)(3)(4) \begin{cases}a & b & c & d & e & f \\ a & d & e & b & c & f \end{cases}\} = (a)(b d)(c e)(f)  4
⋮
(1 2)(3 4) \begin{cases}a & b & c & d & e & f \\ a & e & d & c & b & f \end{cases}\} = (a)(b e)(c d)(f)  4

There are 6 permutations in S_{4} of the shape (α β γ δ), 8 permutations of the shape (α)(β γ δ), 6 permutations of the shape (α β)(γ)(δ), and 3 permutations of the shape (α β)(γ δ). There is also the identity. From the cycle numbers of the corresponding induced permutation representation according to the table above, we obtain

|G \\ X| = \frac{1}{24}(1 · 2^{6} + 3 · 2^{4} + 6 · 2^{4} + 6 · 2^{2} + 8 · 2^{2}) = 11.

Exercise 3 How many necklaces with 5 beads in at most 3 colors are there?

Let C_{5} act on X := {R, G, B}^{[5]} by σf := f ∘ σ^{−1}. We have C_{5} = ⟨π⟩ with π = (1 2 3 4 5) and

π^{0} = (1)(2)(3)(4)(5),
π^{1} = (1 2 3 4 5),
π^{2} = (1 2 3 4 5) ∘ (1 2 3 4 5) = (1 3 5 2 4),
π^{3} = (1 3 5 2 4) ∘ (1 2 3 4 5) = (1 4 2 5 3),
π^{4} = (1 4 2 5 3) ∘ (1 2 3 4 5) = (1 5 4 3 2),
π^{5} = (1 5 4 3 2) ∘ (1 2 3 4 5) = (1)(2)(3)(4)(5) = π^{0}.

It follows that

|C_{5} \\ \{R, G, B\}^{[5]}| = \frac{1}{|C_{5}|} ∑_{σ∈C_{5}} |X_{σ}| = \frac{1}{5}(3^{5} + 3 + 3 + 3 + 3) = 255/5 = 51.

Exercise 4 How many bracelets with 5 beads in at most 3 colors are there?

Let D_{5} act on X := {R, G, B}^{[5]} by σf := f ∘ σ^{−1}. We have D_{5} := ⟨π, τ⟩ with

π = (1 2 3 4 5)  and  τ = (2 5)(3 4).

The elements of D_{5} are therefore (see also Exercise 3):

π^{0} = (1)(2)(3)(4)(5),  τ ∘ π^{0} = (2 5)(3 4)(1),
π^{1} = (1 2 3 4 5),  τ ∘ π^{1} = (2 5)(3 4)(1) ∘ (1 2 3 4 5) = (1 5)(2 4)(3),
π^{2} = (1 3 5 2 4),  τ ∘ π^{2} = (2 5)(3 4)(1) ∘ (1 3 5 2 4) = (1 4)(2 3)(5),
π^{3} = (1 4 2 5 3),  τ ∘ π^{3} = (2 5)(3 4)(1) ∘ (1 4 2 5 3) = (1 3)(2)(4 5),
π^{4} = (1 5 4 3 2),  τ ∘ π^{4} = (2 5)(3 4)(1) ∘ (1 5 4 3 2) = (1 2)(3 5)(4).

It follows that

|D_{5} \\ \{R, G, B\}^{[5]}| = \frac{1}{|D_{5}|} ∑_{σ∈D_{5}} |X_{σ}| = \frac{1}{10}(3^{5} + 5 · 3^{3} + 4 · 3) = 39.

Exercise 5 How many bracelets with 6 beads in at most 3 colors are there? Let D_{6} act on X := {R, G, B}^{[6]} by σf := f ∘ σ^{−1}. We have D_{6} = ⟨π, τ⟩ with

π = (1 2 3 4 5 6) and τ = (1 6)(2 5)(3 4).

The elements of D_{6} are therefore

π^{0} = (1)(2)(3)(4)(5)(6),  τ ∘ π^{0} = (1 6)(2 5)(3 4),
π^{1} = (1 2 3 4 5 6),  τ ∘ π^{1} = (1 5)(2 4)(3)(6),
π^{2} = (1 3 5)(2 4 6),  τ ∘ π^{2} = (1 4)(2 3)(5 6),
π^{3} = (1 4)(2 5)(3 6),  τ ∘ π^{3} = (1 3)(2)(4 6)(5),
π^{4} = (1 5 3)(2 6 4),  τ ∘ π^{4} = (1 2)(3 6)(4 5),
π^{5} = (1 6 5 4 3 2),  τ ∘ π^{5} = (1)(2 6)(3 5)(4).

It follows that

|D_{6} \\ X| = \frac{1}{|D_{6}|} ∑_{σ∈D_{6}} |X_{σ}| = \frac{1}{12}(1 · 3^{6} + 3 · 3^{4} + 4 · 3^{3} + 2 · 3^{2} + 2 · 3^{1}) = 92.