The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Class 3: Multinomials and Inclusion-Exclusion – Answers
Q1: (a)
�
7
3
�
= 7!
3! 4!
= 7 · 5 = 35.
(b) See lectures.
(c)
⇣
10
3,3,1,2
⌘
= 10!
4! 3! 1! 2!
= 12600.
(d) The multinomial coe�cient
⇣
n
k1,k2,n�k1�k2
⌘
counts the number of ways to choose n
elements such that k1 goes into box 1 (labelled s) k2 goes into box 2 (labelled t) and the
remaining n� k1 � k2 elements goes into box 3 (labelled 1).
Q2: (a) Make a bijection such that an element xj from the set is associated with box j and
place a block into box j each time the element xj is selected.
(b)
�
8+4�1
4
�
= 11!
4! 7!
= 11⇥10⇥9⇥8
4!
= 11⇥ 10⇥ 3 = 330.
Q3: (a) Total = 11
(b) Latin only = 1
(c) Russian only = 3.
Q4: (a)
✓
6
2, 2, 2
◆
=
6!
2!2!2!
= 90.
(b)
(i) # (arrangements with one pair always in succession) =
✓
5
2, 2, 1
◆
=
5!
2!2!1!
= 30.
(ii) # (arrangements with two pairs always in succession) =
✓
4
2, 1, 1
◆
=
4!
2!1!1!
= 12.
iii) # (arrangements with three pairs always in succession) =
✓
3
1, 1, 1
◆
=
3!
1!1!1!
= 6.
(c) #(arrangements with a no pairs of socks in succession) = 30.
Q5: (a) |Pk| = 2! = 2.
(b) Pj \ Pk is the set of permutations where both j and k are fixed, so |Pj \ Pk| = 1 .
(c) |P1 \ P2 \ P3| = 1.
(d) Just plug in from above.
(e) Pr
✓
no one collects
correct umbrella
◆
=
1
3
.