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.