CS计算机代考程序代写 discrete mathematics The University of Melbourne — School of Mathematics and Statistics

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


.