The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Class 10: Symmetric Group and Applications – Answers
Q1: (a) For a permutation written in terms of 2-cycles: sgn = (�1)#(2-cycles).
Count 2-cycles on LHS and RHS and show there is an odd number of these.
(b) Note the action of a transposition is:
• Left action “swaps values”.
• Right action “swaps positions”.
So the left action on 213564 is
(25) � 213564 = 513264 = s4s3s2s3s4 � 213564
for the right action
213564 � (25) = 263514 = 213564 � s4s3s2s3s4
(c) To show that (k + 1 k k + 2) = (k k + 1 k + 2)�1 it su�ces to show
(k + 1 k k + 2) � (k k + 1 k + 2) = I.
Similarly, to show that (k k + 1 k + 2)�1 = (k k + 1 k + 2)2 it su�ces to show
(k k + 1 k + 2)3 = I
(d) A3 = {(123), (123)2, (123)3}.
Q2:
s5s1s2s1 = (56)(12)(23)(12) = (13)(56) =
✓
1 2 3 4 5 6 7
3 2 1 4 6 5 7
◆
s4s5s4s5s1s2s1s4 = (45)(56)(45)(56)(12)(23)(12)(45) = (13)(56) =
✓
1 2 3 4 5 6 7
3 2 1 4 6 5 7
◆
Use (s4s5s4)s5 = (s5s4s5)s5 = s5s4, so
s4s5s4s5s1s2s1s4 = s5s4s1s2s1s4 = s5s4s4s1s2s1 = s5s1s2s1
where the second equality follow since s4 commutes with s1 and s2, and the third follows
from s2
4
= 1.
Q3: (a) The bipartite graph corresponding to � = 42153 is
1
1
2
2
3
3
4
4
5
5
(b) Each crossing in (a) is an inversion. So the 5 crossings results in 5 inversions.
(c) � = s3s4s1s2s1, which has this bipartite graph:
1
1
2
2
3
3
4
4
5
5
s1
s2
s1
s4
s3
(d) I� = {(1, 2), (1, 3), (1, 5), (2, 3), (4, 5)}.
Q4: The desired board position has a snake-pattern permutations of odd parity.
(a) Here the parity is even so the sought after ordering can’t be achieved.
(b) Since the parity is odd the sought after ordering can be achieved.
(c) Since the parity is odd the sought after ordering can be achieved.
Q5: The two snake-pattern permutations have di↵erent parity so board positions cannot be
related by sliding moves.
Q6: Let us make the identifications
R = 1 A = 2 T = 3 E = 4 Y = 5 O = 6 U = 7 R = 8
M = 9 I = 10 N = 11 D = 12 P = 13 A = 14 L = 15 ⇤ = 16
A key point here is that the 2 and 14 are indistinguishable in this particular version of
the 15-puzzle. Consider then the even permutation
(2 14) � (14 15)
which first interchanges the two A’s, then interchanges the A and L. Being even, it is
attainable, and it leaves the last line reading PLA⇤, and the other 3 lines reading as
before.