Problem Set 4
Inclusion-Exclusion, Generating Functions, Recurrences
MAT 344
2022 S
8 April 2022
© Mehmet Durlanik, Zack WolskePage 1
Learning Objectives
These problems relate to the course learning outcomes:
• Select and justify appropriate tools to analyze a counting problem,
• Analyze a counting problem by proving an exact or approximate enumeration, or a
method to compute one efficiently ; and
• Construct counting problems which show the usefulness or limitations of combinato-
rial tools.
1. Give combinatorial proofs of these identities, where dk denotes the number of derange-
ments of [k]:
(a) (
n−m
r −m
)
=
m∑
i=0
(
m
i
)
(−1)i
(
n− i
r
)
.
Hint: consider certain subsets of [n] containing [m].
(b)
n! =
n∑
k=0
(
n
k
)
dk
2. Let an be the sequence with a0 = 0 and
an+1 = 2(n + 1)an + (n + 1)!
Find and prove a closed formula for an, depending only on n.
3. Let fn be the number of strings of length n using the letters A,B,C,D, such that
there are an even number of As; 1, 2, 3 or 4 Bs; either 2 or 5 Cs; and at least 1 D. So
f0 = f1 = f2 = f3 = 0, while f4 = 12 and f5 = 60. Find a generating function for fn,
and explain how you got it.
4. In English, the word “buffalo” can be used as a verb, a common noun, or a place name.
This leads to a linguistic puzzle where “Buffalo buffalo buffalo . . . buffalo.” with n
“buffalo”s can be interpreted as a meaningful sentence. However, these sentences may
not have a unique interpretation. Let bn denote the number of ways to interpret the
sentence, and take b0 = b1 = 1. The sequence satisfies the recurrence
bn = b0bn−2 + b1bn−3 + b2bn−4 + · · · + bn−2b0 =
n−2∑
k=0
bkbn−2−k.
• Find a generating function for bn that does not contain an infinite series.
• Use your generating function to find br, where r is the last two digits of your
student number.
5. Give an example of a counting problem that can be analyzed using inclusion-exclusion
or generating functions, and explain your analysis.