MAST30012 Discrete Mathematics

Semester 2, 2022

Assignment 3

Due 11:59pm Monday October 17

Q1: (8 marks)

(a) Using only formal power series manipulations (e.g. addition, multiplication, differentiation) of the geometric series

find expressions for

i. A(x), the generating function for the sequence an = n3 - n for n ≥ 0, and

ii. B(x), the generating function for the sequence for n ≥ 0.

(b) Find an explicit expression for bn  (i.e. a polynomial in n).

Q2: (11 marks)

Let T be the set of lattice paths which

• take steps from the step set {(1, 2), (1, -1)}, and

• start at the origin (0, 0), remain on or above the line y = 0, and end on the line y = 0.

Let Tn  be those paths in T with n steps, and let tn  = |Tn|.  The path with no steps is a valid path, so t0 = 1.

(a) Explain why tn = 0 if n is not a multiple of 3.

(b)  Draw the paths in T3 and T6.

(c) If T(x) is the generating function for the sequence tn, find a functional equation satisfied by T(x), and explain what each term in the functional equation means.  (Hint: this equation should be cubic in T(x).) Do not try to solve the equation!

(d)  Remember that Dyck paths and binary trees are both counted by the Catalan numbers.  The paths in Tn  are also in bijection with a certain set of trees.  Explain what this set of trees is. The n in Tn  refers to the number of steps in a path – what is the corresponding meaning of n for the set of trees?

(e) If the step set {(1, 2), (1, -1)} is replaced with {(1, k), (1, -1)} for an integer k  ≥  1, what happens to the functional equation you found in (c)?

Q3: (11 marks)

Starting from the word ‘keyboard’, rearrange the letters to get ‘drakeboy ’.

(a) Let the permutation τ correspond to the arrangement (so the letter in position i moves to position τi). Write τ as a two-line array.

(b) Let the permutation σ correspond to the map (so the letter in position i becomes the letter in position σi). Write σ as a two-line array.

(c) What is the relationship between τ and σ?

(d) Write τ in standard cycle format.

(e) What is the parity of τ?

(f) What is the smallest value of n such that τn = id (the identity permutation)?

(g) Write τ as a product of transpositions.

(h)  Represent σ as a bipartite graph (please don’t make it too small!)

(i)  How is the number of inversions in σ related to the bipartite graph?  How many inversions does σ have?

(j) Write down the set of inversions Iσ of σ.