The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Class 9: Permutations – Answers
Q1: (i) 264351 =
✓
1 2 3 4 5 6
2 6 4 3 5 1
◆
= (126)(34) = (16)(12)(34)
(ii) 315642 =
✓
1 2 3 4 5 6
3 1 5 6 4 2
◆
= (135462) = (12)(16)(14)(15)(13)
Q2: (i) (i) An r-cycle � can be written as the product of r� 1 2-cycles so sgn(�) = (�1)r�1.
(ii) � = 87654321 = (18)(27)(36)(45), ⌧ = 46213875 = (14)(26853).
(iii) sgn(�) = +1, sgn(⌧) = ;= �1.
(iv) (156)(247)(38) =
✓
1 2 3 4 5 6 7 8
5 4 8 7 6 1 2 3
◆
(1587)(23)(46) =
✓
1 2 3 4 5 6 7 8
5 3 2 6 8 4 1 7
◆
Q3: � = s5s4s3s1s2s1 =
✓
1 2 3 4 5 6
1 2 4 6 3 5
◆
Q4: (123)(234)(324) =
✓
1 2 3 4
2 3 1 4
◆
(213)(324)(324) =
✓
1 2 3 4
3 2 4 1
◆
.
Q5: (i) An(x) =
nX
k=0
S1(n, k)x
k = (n� 1)
nX
k=0
S1(n� 1, k)xk +
nX
k=0
S1(n� 1, k � 1)xk.
Now rewrite each term and prove
An(x) = (n� 1)An�1(x) + xAn�1(x) = (x+ n� 1)An�1(x).
(ii) A0(x) = S1(0, 0) = 1
A1(x) = xA0(x) = x
A2(x) = (x+ 1)A1(x) = (x+ 1)x
A3(x) = (x+ 2)A2(x) = (x+ 2)(x+ 1)x
…
An(x) = (x+ n� 1)An�1(x) = (x+ n� 1)(x+ n� 2) · · · (x+ 2)(x+ 1)x
Q6: We have to seat n people at n� 2 tables. There are two cases:
Case 1: Three people are seated at one table the remaining n � 3 people must then be
seated one each at the remaining n� 3 tables. There are 2
�
n
3
�
seating arrangements for
this case.
Case 2: Two people each are seated at two of the tables with the remaining n� 4 seated
one each at the remaining n � 4 tables. There are 1
2
�
n
2
� �
n�2
2
�
seating arrangements for
this case.
Putting everything together we have: S1(n, n� 2) = 2
✓
n
3
◆
+
1
2
✓
n
2
◆✓
n� 2
2
◆
.