Manuel Kauers Hagenberg, April 22, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 6

Exercise 1 Show: Any equivalence relation ∼ on a set M can be induced by a suitably defined group action G × M → M.

We assume that M is countable. Let ∼ be an equivalence relation on M,

M/∼ = {[m]_{∼} : m ∈ M}.

Let [m_{1}]_{∼}, [m_{2}]_{∼}, … be a (possibly finite) enumeration of M/∼, and let M_{i} denote the cardinality of [m_{i}]_{∼} (i ∈ ℕ). Consider the additive group G = ℤ_{M_{1}} × ℤ_{M_{2}} × … (with ℤ_{M_{i}} := ℤ if M_{i} = ∞). By writing

[m_{i}]_{∼} := \{ \begin{matrix}\{m_{i,0}, m_{i,1}, …, m_{i,M_{i}−1}\} & if M_{i} < ∞ \\ \{…, m_{i,−1}, m_{i,0}, m_{i,1}, … \} & if M_{i} = ∞ \end{matrix} ,

and defining

(π_{1}, π_{2}, …)m_{i,j} := \{ \begin{matrix}m_{i,j+π_{i} mod M_{i}} & if M_{i} < ∞ \\ m_{i,j+π_{i}} & if M_{i} = ∞ \end{matrix}

for (π_{1}, π_{2}, …) ∈ G we obviously obtain a group action on M with G \\ M = M/∼. That’s it.

Exercise 2

a) How many lecklaces of six beads are there where exactly two beads are red, two beads are green, and two beads are blue?

b) Try to come up with a corresponding group action description of the problem.

c) How many necklaces of six beads in at most three colors are there?

Ad a) I found the following 16 ones:

1. R R G G B B

2. R R G B G B

3. R R G B B G

4. R R B B G G 5. R R B G B G

6. R R B G G B

7. R G R B B G

8. R G R B G B 9. R G R G B B 10. R B R G G B 11. R B R G B G 12. R B R B G G 13. R B B R G G 14. R B G R B G 15. R B G R G B 16. R G B R G B

Ad b) In a first step, we model the situation with distinct beads. Consider

ℤ_{6} × S_{6} → S_{6}, (πf)(n) ↦ f(n + π mod 6).

Then ℤ_{6} \\ S_{6} is a group action description for the necklaces (strings up to cyclic rotation) with six different beads. In the next step, we will identify pairs of beads in order to model the color. Say, the beads 1 and 2 are red, 3 and 4 are green, and 5 and 6 are blue. Let G = ℤ_{2}×ℤ_{2}×ℤ_{2} act on ℤ_{6} \\ S_{6} via

G × (ℤ_{6} \\ S_{6}) → ℤ_{6} \\ S_{6}

((π_{1}, π_{2}, π_{3})f)(n) := \{ \begin{matrix}f(π_{1}(n)) & n ∈ \{1, 2\} \\ f(2 + π_{2}(n − 2)) & n ∈ \{3, 4\} \\ f(4 + π_{3}(n − 4)) & n ∈ \{5, 6\} \end{matrix}

where f is a representative of an orbit [f]_{∼} ∈ ℤ_{6} \\ S_{6} and the elements of ℤ_{2} are considered as permutations of pairs in the obvious way. Observe that the definition is also independent of the choice of the representative, because the rotation of ℤ_{6} and swaping of G commute. Also observe that we have defined a group action. For,

(1_{G}f)(n) = ((0, 0, 0)f)(n)
(σ(πf))(n) = \{ \begin{matrix}(πf)(σ_{1}(n)) & n ∈ \{1, 2\} \\ 2 + (πf)(σ_{2}(n − 2)) & n ∈ \{3, 4\} \\ 4 + (πf)(σ_{3}(n − 4)) & n ∈ \{5, 6\} \end{matrix}

= \{ \begin{matrix}π_{1}(σ_{1}(n)) & n ∈ \{1, 2\} \\ 2 + π_{2}(σ_{2}(n − 2)) & n ∈ \{3, 4\} \\ 4 + π_{3}(σ_{3}(n − 4)) & n ∈ \{5, 6\} \end{matrix}

= (πσ)f(n).

We used that σ_{i}({1, 2}) = {1, 2} and that ℤ_{2} is commutative.

Ad c) I found the following 130 ones:

1. B B B B B B

2. B B B B B G

3. B B B B B R

4. B B B B G G

5. B B B B G R

6. B B B B R G

7. B B B B R R

8. B B B G B G

9. B B B G B R

10. B B B G G G

11. B B B G G R

12. B B B G R G

13. B B B G R R

14. B B B R B G

15. B B B R B R

16. B B B R G G

17. B B B R G R

18. B B B R R G

19. B B B R R R

20. B B G B B G

21. B B G B B R

22. B B G B G G

23. B B G B G R 24. B B G B R G 25. B B G B R R 26. B B G G B G 27. B B G G B R 28. B B G G G G 29. B B G G G R 30. B B G G R G 31. B B G G R R 32. B B G R B G 33. B B G R B R 34. B B G R G G 35. B B G R G R 36. B B G R R G 37. B B G R R R 38. B B R B B R 39. B B R B G G 40. B B R B G R 41. B B R B R G 42. B B R B R R 43. B B R G B G 44. B B R G B R 45. B B R G G G 46. B B R G G R 47. B B R G R G 48. B B R G R R 49. B B R R B G 50. B B R R B R 51. B B R R G G 52. B B R R G R 53. B B R R R G 54. B B R R R R 55. B G B G B G 56. B G B G B R 57. B G B G G G 58. B G B G G R 59. B G B G R G 60. B G B G R R 61. B G B R B R 62. B G B R G G 63. B G B R G R 64. B G B R R G 65. B G B R R R 66. B G G B G G 67. B G G B G R 68. B G G B R G 69. B G G B R R 70. B G G G B R 71. B G G G G G 72. B G G G G R 73. B G G G R G 74. B G G G R R 75. B G G R B R 76. B G G R G G 77. B G G R G R 78. B G G R R G 79. B G G R R R 80. B G R B G R 81. B G R B R G 82. B G R B R R 83. B G R G B R 84. B G R G G G 85. B G R G G R 86. B G R G R G 87. B G R G R R 88. B G R R B R 89. B G R R G G 90. B G R R G R 91. B G R R R G 92. B G R R R R 93. B R B R B R

94. B R B R G G

95. B R B R G R

96. B R B R R G

97. B R B R R R

98. B R G B R G

99. B R G B R R

100. B R G G G G

101. B R G G G R

102. B R G G R G 103. B R G G R R 104. B R G R G G 105. B R G R G R 106. B R G R R G 107. B R G R R R 108. B R R B R R 109. B R R G G G 110. B R R G G R 111. B R R G R G 112. B R R G R R 113. B R R R G G 114. B R R R G R 115. B R R R R G 116. B R R R R R 117. G G G G G G 118. G G G G G R 119. G G G G R R 120. G G G R G R 121. G G G R R R 122. G G R G G R 123. G G R G R R 124. G G R R G R 125. G G R R R R 126. G R G R G R 127. G R G R R R 128. G R R G R R 129. G R R R R R 130. R R R R R R

Exercise 3 Let Y be a G-set and X be a set. Define

G × Y^{X} → Y^{X}, (π, f) ↦ πf

by

(πf)(x) = π(f(x)) (x ∈ X).

Show that this is a group action.

Let π_{1}, π_{2} ∈ G, x ∈ X, f ∈ Y^{X}. Then

(1_{G}f)(x) = 1_{G}(f(x)) = f(x)

and (π_{1}(π_{2}(f)))(x) = π_{1}((π_{2}f)(x)) = π_{1}(π_{2}(f(x))) = (π_{1} ∘ π_{2})(f(x)).

Note that both times the last step makes use of the fact that X is a G-set.