The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Class 8: Catalan and Functional Equations – Answers
Q1: Bijections to balanced parentheses or Dyck paths are clear.
Q2: (a) These are the possible diagrams on 2n points for n = 1, 2, 3:
(b) Take points labelled i and j > i and consider a chord between the points.
(c) Bijection between chord diagrams on 2n points and balanced parenthesis:
Go through the points is order of labelling and record
• An opening parenthesis ‘(’ i↵ the chord goes to a point of higher label.
• A closing parenthesis ‘)’ i↵ the chord goes to a point of lower label.
(d) Label points 1 up to 2n counter-clockwise.Draw a chord from the point 1 to the
point 2j.
Show this gives rise to the Catalan recurrence.
Similar consideratiosn gives the Catalan functional equation.
Q3: (a) There are 9 possible diagrams on n = 4 points:
(b) Motzkin paths are lattice paths in N2
0
with step set S = {(1, 0), (1, 1), (1,�1)}, which
we shall refer to as Right, Up and Down steps, respectively.
A bijection between chord diagrams on n points and Motzkin paths with n steps, is:
Go through the points is order of labelling and record
• ‘Right’ step i↵ there is no chord from the point.
• ‘Up’ step i↵ there is a chord from the point to a point of higher label.
• ‘Down’ step i↵ there is a chord from the point to a point of lower label.
(c) There can be zero points on the circle giving a contribution 1.
Otherwise, we ‘partition’ on the point labelled 1. There are two cases.
Case 1: There is no chord from the first point.
Case 2: There is a chord from the first point to some other point on the circle.
This takes care of all the possible cases. Adding up all the contributions we have:
C(x) = 1 + xC(x) + x2C(x)2.
Q4: Di↵erentiate term-by-term and consider the e↵ect on xn
x
k d
k
dxk
x
n = xkn
dk�1
dxk�1
x
n�1 = xkn(n� 1) · · · (n� k + 1)xn�k = nkxn.
The combinatorial interpretation is that xk d
k
dxk
L(x) counts lattice paths with k distinct
steps marked and labelled (from 1 to k) in the order in which they were singled out.
Similarly
✓
x
d
dx
◆k
x
n =
✓
x
d
dx
◆k�1 ✓
x
d
dx
◆
x
n = n
✓
x
d
dx
◆k�1
x
n = nkxn.
The combinatorial interpretation is that the generating function (x d
dx
)kL(x) counts lattice
paths where we have marked k steps and labelled them (from 1 to k) in the order in which
they were singled out but each step could be chosen (labelled) many times.
Now k! counts the number of ways of arranging k elements in a line (permutations) so
dividing by k! ‘gets rid of’ the ordering of the marking of the k steps, i.e., 1
k!
x
k dk
dxk
L(x)
counts lattice paths where we have simply marked k distinct steps.
Q5: Using our working (interpretations) from Q4 we have
(a) x
d
dx
✓
1
1� x� y
◆
=
x
(1� x� y)2
.
(b) y
d
dy
✓
x
d
dx
✓
1
1� x� y
◆◆
= y
d
dy
✓
x
(1� x� y)2
◆
=
2xy
(1� x� y)3
(c)
1
3!
x
3
d3
dx3
✓
1
1� x� y
◆
=
x
3
(1� x� y)4
Q6: (a) Integrate term-by-term and and manipulate.
(b) Use convolution of generating functions.
an =
1
4n
✓
2n
n
◆
.