University of Waterloo

MATH 239 Midterm Examination

Term: Winter Year: 2024
Course number: MATH 239
Course title: Introduction to
Combinatorics Last name:
Sections: 001, 002, 003, 004
Instructors: D. Gosset, K. Hare, First name:
O. Mandelshtam, S. Spirkl
Date of exam: March 7, 2024
Exam period: 4:30 PM to 6:20 PM ID number:
Duration of exam: 110 minutes
Number of pages: 11 (includes cover page) Waterloo user id:
Exam type: Closed book
Materials allowed: None

Additional instructions:

1. No calculators or any other aids may be used.

2. For multiple choice / true/false questions, mark your answer on the included bubble sheet.

3. For written questions, write your answers in the space provided. If you need more room, use the
blank pages at the end and clearly indicate this on the question.

4. Your exam paper will be scanned in greyscale, and only the scanned copy will be marked. Do not
rely on colour in your solutions. Do not write too close to the margins.

5. All answers must be justified, unless otherwise stated.

6. Unless otherwise stated, you may use any result proved or stated in class but you should be
explicit about which result you are using. You can refer to a theorem by name or number, or
describe the theorem (“By the theorem that says ‘if X then Y’...”).

7. Good luck!

Question values:

Question: 1 2 3 4 5 6 7 Total
Points: 16 4 7 8 5 7 7 54
Note: All graphs in this exam are assumed to be undirected, and have no multiple edges or loops.

Multiple choice questions

Instructions for multiple choice questions: Pages 2 and 3 will not be marked. Enter your answer
by filling in the appropriate bubble on the multiple choice bubble sheet included at the end of the
booklet. You do not have to provide any justification of your answers.

1. (a) (2 points) Which of the following functions is invertible over C? (A(x) is invertible over C if and
only if there exists a formal power series B(x) with coefficients in C such that A(x)B(x) = 1.)
x
A. A(x) = 1−x 2
1+2x
⋆ B. ⋆ A(x) = 1−x−x2
1 1
C. A(x) = 1−x
− 1−2x
n 2n+1
P
D. A(x) = n≥0 3 x

(b) (2 points) The number of compositions of n with k parts is equal to

A. n+k−1


k−1
n


B. k−1
C. n−1


k
D. n+k


k−1
⋆ E. ⋆ n−1


k−1

(c) (2 points) Let A be a set with a weight function w : A → N, and let A(x) := Φw A (x) be the
corresponding generating series. Define a new weight function v : A → N by v(a) = 2w(a) + 3.
Then the generating series of A with respect to v is given by:
A. ΦvA (x) = A(2x + 3)
B. ΦvA (x) = A(x2 + 3)
C. ΦvA (x) = x3 (A(x))2
D. ΦvA (x) = (A(x))2 + 3
⋆ E. ⋆ ΦvA (x) = x3 A(x2 )

(d) (2 points) Let S and T be sets of binary strings with cardinalities |S| = s and |T | = t. Then
the cardinality of the concatenation product ST is st.
A. True.
⋆ B. ⋆ False.

x4
(e) (2 points) The coefficient [x2024 ] equals
(1 − 3x2 )6
A. 1010

1010
5
3
⋆ B. ⋆ 1015

1010
3

5
1015 1015
C. 5 3
D. 1015

2020
5
3
1016 1010


E. 6 3

Page 2
(f) (2 points) Let G be a k-regular graph with 10 vertices and 60 edges. Then k must be
A. 6
⋆ B. ⋆ 12
C. 3
D. 8
E. 16

(g) (2 points) Let G be a graph on four vertices with degrees 3, 2, 2, 1. Then G is necessarily
isomorphic to the graph below:
C

A B
⋆ A. ⋆ True
B. False

(h) (2 points) Let A be the set of binary strings with exactly two 0s. Let the weight function be
ω : A → N where ω(a) be the number of 1s in a. The generating series ΦωA (x) is
1
A. ΦωA (x) = (1−x)2

x2
B. ΦωA (x) = (1−x)3
x2
C. ΦωA (x) = (1−2x)3
1
⋆ D. ⋆ ΦωA (x) = (1−x) 3

ω 1
E. ΦA (x) = (1−2x)3

Page 3
2. (4 points) Let S be the set of compositions consisting of at least 2 parts and where all parts are
congruent to 1 modulo 3. Find the generating series for S weighted by size.
Simplify your answer to a single rational function; that is, your answer should be in the form
P (x)/Q(x) where P (x) and Q(x) are polynomials. You do not need to fully expand P (x) and Q(x).

Solution:
Each part is an element of the set P = {1, 4, 7, . . .} = {3k + 1 : k ∈ N}. The generating function
for a single part is X x
ΦP (x) = x3k+1 = 3
.
k≥0
1 − x

Now, since S has at least two parts, we can write

S = P 2 × P ∗.

P has no weight-0 elements, so we can apply the String lemma to get

1 1 1 − x3
ΦP ∗ (x) = = x = .
1 − ΦP ∗ (x) 1 − 1−x 3 1 − x − x3

With the Product lemma, this gives

x2 (1 − x3 ) x2
ΦS (x) = ΦP (x)2 ΦP ∗ (x) = = .
(1 − x − x3 )(1 − x3 )2 (1 − x − x3 )(1 − x3 )

Marking scheme.

• 1 point for generating function of P,

• 1 point for decomposition of S,

• 0.5 for invoking String and Product lemmas,

• 1.5 for final answer (take off 0.5-1 for computation errors).

Page 4
3. (7 points) For parts (a) and (b), you don’t need to prove the expressions you provide are unam-
biguous, but do include a short (1-2 sentences) justification.
(a) Write an unambiguous regular expression for the set of binary strings with an even number of
blocks. (Note: zero is an even number)
(b) Write an unambiguous regular expression for the set of binary strings with an odd number of
blocks.
(c) Show that for all n ≥ 2, the number of binary strings of length n with an even number of
blocks equals the number of binary strings with an odd number of blocks.

Solution:
(a) Strings with an even number of blocks either start with a block of 0’s and end with a block
of 1’s which is given by the regex (0∗ 01∗ 1)∗ or start with a block of 1’s and end with a
block of 0’s with the regex 1∗ 1(0∗ 01∗ 1)∗ 0∗ 0; we make sure the second one is necessarily
nonempty so we don’t duplicate the empty string. Thus we have the regex:
(0∗ 01∗ 1)∗ ⌣ 1∗ 1(0∗ 01∗ 1)∗ 0∗ 0

(b) Strings with an odd number of blocks are necessarily nonempty and either start with a
block of 0’s and end with a block of 0’s which is given by the regex 0∗ 0(1∗ 10∗ 0)∗ or start
with a block of 1’s and end with a block of 1’s with the regex 1∗ 1(0∗ 01∗ 1)∗ . Thus we have
the regex:
0∗ 0(1∗ 10∗ 0)∗ ⌣ 1∗ 1(0∗ 01∗ 1)∗
(c) We compare the generating functions ΦE (x) and ΦO (x) produced from the regular expres-
sions in (a) and (b), respectively:
x

2
1 1−x (1 − x)2 + x2 1 − 2x + 2x2
ΦE (x) =
2 +
2 = =
x
1 − 1−x 1 − 1−xx (1 − x)2 − x2 1 − 2x
x
1−x 2x(1 − x) 2x − 2x2
ΦO (x) = 2
2 = =
1 x
− 1−x (1 − x)2 − x2 1 − 2x
Now, for n ≥ 2,
1 − 4x + 4x2
 
n n
[x ](ΦE (x) − ΦO (x)) = [x ] = [xn ](1 − 2x) = 0.
1 − 2x
Thus we have, as desired:
[xn ]ΦO (x) = [xn ]ΦE (x).
Alternative solution. Fix n ≥ 2 and let O and E be the sets of binary strings of length
n with an odd and even number of blocks, respectively. We show there is a bijection
f : O → E that flips the last bit to change the number of blocks: f (a1 · · · an ) = a′1 · · · a′n
where a′i = ai for 1 ≤ i < n, and a′n = 1 − an . Then if an−1 = an , f (a1 · · · an ) has 1 more
block than a1 · · · an , and otherwise it has 1 fewer blocks. Thus f indeed changes the parity
of the number of blocks, and thus is well-defined. Since f (f (a1 · · · an )) = a1 · · · an , f is its
own inverse, and thus a bijection.
Marking scheme.
(a) 2 points: 1 for the regex, 1 for a brief explanation (mentioning block decomposition, starting
with 0 or 1, including/excluding the empty string, etc.)
(b) 2 points, same as (a)
(c) 3 points: either for comparing the generating series, or for providing a bijection.
Comparing the generating series: 1 point for ΦE , 1 pooint for ΦO , 1 point for showing
they’re equal.
Bijection: 1 point for stating the bijection, 1 point for explaining why it changes the
parity, 1 point for stating it’s its own inverse.

Page 5
4. (8 points) Let bn = [xn ]B(x) for all n ≥ 0, where

2 − 15x − 11x2
B(x) =
(1 + x)2 (1 − 5x)
(a) Derive a linear recurrence that determines the coefficients bn for n ≥ 3, and solve for b0 , b1 ,
and b2 .
(b) Use the partial fraction decomposition method to obtain an explicit expression for bn for n ≥ 0.

Solution:
(a) Expand the denominator as 1 − 3x − 9x2 − 5x3 . Then

(1 − 3x − 9x2 − 5x3 )B(x) = 2 − 15x − 11x2

Equating coefficients of xn for n = 0, 1, 2, we get

b0 = 2
−3b0 + b1 = −15
−9b0 − 3b1 + b2 = −11,

and therefore b0 = 2, b1 = −9, b2 = −20. Equating coefficients of xn for n ≥ 3 gives the

recurrence
−5bn−3 − 9bn−2 − 3bn−1 + bn = 0.

(b) The partial fractions expansion is

B(x) = a/(1 + x)2 + b/(1 + x) + c/(1 − 5x).

To solve for the coefficients we plug in values of x:

B(0) = 2 = a + b + c (1)
B(1) = 3/2 = a/4 + b/2 − c/4 (2)
B(2) = 8/9 = a/9 + b/3 − c/9 (3)

The solution is a = 1, b = 2, c = −1. Using the negative binomial series and the geometric
series we get

[xn ]B(x) = 2 · (−1)n + (−1)n (n + 1) − (5)n = (n + 3) · (−1)n − 5n .

Marking scheme.
(a) 2 marks for recurrence, 2 marks for initial values

(b) 2 mark for correct form of partial fractions expansion, 2 marks for correctly solving for
the coefficients.

Page 6
5. (5 points) Define the GHMS-graph G on vertices V (G) = {v1 , v2 , . . . , vn } by the rule that {v1 , v2 } ∈
E(G) if and only if |v1 − v2 | ≥ 2.
Let G1 , G2 , and G3 be GHMS-graphs with

V (G1 ) = {1, 2, 3, 4}, V (G2 ) = {1, 3, 4, 5}, and V (G3 ) = {1, 2, 3, 5}.

(a) Draw the three GHMS-graphs G1 , G2 , and G3 .

(b) For the GHMS-graphs G1 and G2 , either demonstrate an isomorphism, or explain why they
are not isomorphic.
(c) For the GHMS-graphs G2 and G3 , either demonstrate an isomorphism, or explain why they
are not isomorphic.

Solution:

1 1 1

2 3 3 4 2 3

(a)
4 5 5
(b) We see G1 has 3 edges, whereas G2 has four. Hence they are not isomorphic. We could
have also noticed that G1 is bipartite, or G1 is a tree, whereas G2 is neither of these things.

(c) Consider the bijection f : V (G2 ) → V( G3 ) given by

f (1) = 5,
f (3) = 3,
f (4) = 2,
f (5) = 1.

We see that this bijection is edge preserving, hence the two graphs are isomorphic.
Marking scheme. 1 pt for question a. 2 pts for each of question b and c. Base the marks for
question b or c on the graphs they draw in (a). (So if they drew the wrong graph, don’t deduct
points twice). Any argument as to why they are not isomorphic are fine. Basically we are seeing
if they know what things are preserved by isomorphism. To demonstrate it is an isomorphism,
they just need to produce a map that is correct. They do not need to explicitly show each edge
is mapped to an edge, as that is painful, and annoying, and easy to check.

Page 7
6. (7 points) Give a combinatorial proof of the following identity for all positive integers n and k:
  k  
n+k X n−1+i
=
n i=0
n−1

Note: no credit will be given for an algebraic proof.

Hint: It may be helpful to consider the set of subsets of {1, 2, . . . , n + k} of size n and largest element
n + i.

Solution: Let
Sn,n+k = {Ω ⊆ {1, 2, . . . , n + k} : |Ω| = n}
We showed in class that |Sn,n+k | = n+k


n
. Now count in a different way to get the RHS. For
each 0 ≤ i ≤ k, let

Wi = {Ω ∈ Sn,n+k : the largest element of Ω is n + i}

Note that |Wi | = n+i−1

n−1
since every element of Wi contains n + i along with any n − 1 elements
from the set 1, 2, . . . , n + i − 1. Then

Sn,n+k = W0 ∪ W1 ∪ . . . Wk

where all the sets in the union are pairwise disjoint. Therefore
k k  
X X n+i−1
|Sn,n+k | = |Wi | =
i=0 i=0
n−1

Marking scheme. 2 marks for writing down a set with size equal to the LHS, 3 marks for a
correct partition into k + 1 suitable sets (RHS counting) , 1 mark for indicating that we are
using the fact that the unions are disjoint, 1 mark for arriving at the correct answer.

Page 8
7. (7 points) Let S = {a, b, c, . . . , z} be the 26 lowercase letters of the English alphabet. Let T be
the set of strings in S ∗ which do not contain arugula as a substring.
(a) Find a recursive decomposition for the set T . You may introduce additional sets to produce
the decomposition.
(b) As with binary strings, the length of a string is the number of letters it contains. For example,
the weight of the string “arugula” is 7. Find the generating series for S with respect to length.
(c) Use the recursive decomposition in part (a) to find the generating series for T with respect to
length.

Solution:

(a) Let R be the set of words in S ∗ which have exactly one occurrence of arugula, as a
suffix. Then: T ∪ R = {ε} ∪ T S since adding another letter to the end of T will result in
either a string in T or a string with exactly one occurrence of arugula, as a suffix. Also,
R{ε, rugula} = T {arugula}, since arugula overlaps itself at the first letter.

(b) Since S contains 26 strings, each of length 1, the generating series is 26x.

(c) Let’s write r(x) for the generating series of r, and write t(x) for the generating series of T .
From the unambiguous recursive decomposition in (a), we have:

t(x) + r(x) = 1 + 26xt(x)

and
r(x)(1 + x6 ) = t(x)x7 .
Plugging the first equation (rearranged for r) into the second gives:

(1 + (26x − 1)t(x))(1 + x6 ) = t(x)x7

so
t(x)((1 − 26x)(1 + x6 ) + x7 ) = 1 + x6
and finally:
1 + x6
t(x) = .
(1 − 26x)(1 + x6 ) + x7

Marking scheme.
(a) 3 marks: 1 for T ∪ R = {ε} ∪ T S, 1 for R{ε, rugula} = T {arugula}, 1 for a brief
explanation (0.5 for each expression)

(b) 1 mark: if they computed the series for S ∗ , that’s fine too.

(c) 3 marks: 1.5 for the functional equations, 1.5 for final answer. If they ”guessed” the correct
expression by adapting the theorem for binary strings, there should be a brief explanation
for how they adapted it.

Page 9
 Additional space for scrap work or answers
If continuing an answer, please indicate in the original question that your answer continues here and
clearly label your answer on this page.

Page 10
 Additional space for scrap work or answers
If continuing an answer, please indicate in the original question that your answer continues here and
clearly label your answer on this page.

Page 11