Math 3152 –

Review problems – solutions December 15, 2017

1. Use the binomial theorem to prove that, for all n ≥ 1 and k satisfying 0 ≤
k ≤ n,
n    (
X n i 1 if k = n;
(−1)i−k =
i k 0 otherwise.
i=k

Solution: Using the binomial theorem twice, we can expand

n  
n
X n
(1 + (t − 1)) = (t − 1)i
i=0
i
n X i   
X n i k
= t (−1)i−k
i=0
i k
k=0

Look at the coefficient of tk in this expansion: from above, that is

n    n   
X n i X n i
(−1)i−k = (−1)i−k ,
i=0
i k i k
i=k

since the terms with i < k are zero.

On the other hand, (1 + (t − 1))n = tn , so this coefficient is zero, unless k = n. This
proves what we wanted.

2. Consider the sequence given by h0 = 1 and the rule that, for n ≥ 1,

(
8 if n is even;
hn = 3hn−1 +
0 otherwise.

(a) Find a generating function for the sequence 8, 0, 8, 0, 8, . . ..

Solution:

8 + 8t2 + 8t4 + · · · = 8(1 + t2 + t4 + · · · )

= 8/(1 − t2 ).
∞
hn xn . Use the recurrence relation to find a formula for
P
(b) Let H(x) =
n=0
H(x).
hn−1 tn = tH(t), the recurrence relation says
P
Solution: Since n≥1

H(t) = h0 + 3tH(t) + 8t2 /(1 − t2 ),

 by the previous part. Since h0 = 1, solving for H(t) gives

H(t) = (1 − 3t)−1 (1 + 8t2 /(1 − t2 ))

1 + 7t2
= .
(1 − 3t)(1 − t2 )

(c) Use the previous part to write hn in terms of n.

Solution: Use partial fractions to find
2 2 1
H(t) = − + .
1 − 3t 1 − t (1 + t)

Then
hn = 2 · 3n − 2 + (−1)n .

3. (a) In how many ways can seven shifts be assigned to ten nurses, if each
nurse can take at most three shifts, and the shifts are all different?
Solution: We assume that a shift is taken by exactly one nurse. So, without the
condition that a nurse can take at most three shifts, we could choose the nurse
for each shift independently, in 107 ways total.
The actual answer is smaller. Let E be the set of assignments of a nurse to a
shift with no condition, and Ai the set of assignments for which nurse i works 4
or more shifts, for 1 ≤ i ≤ 10. We want to know the value of
 10 
[ 
|E| −  Ai  ,
 
 
i=1

for which we use inclusion-exclusion. First, think of Ai as the set of permutations

of length 7 using the multiset of ten nurses (repetition allowed) where the ith
nurse appears at least 4 times.
To compute |Ai |, let’s assign the ith nurse 4 or more shifts first, then place the
other 9 nurses on the remaining shifts.
This gives
       
7 3 7 2 7 1 7
|Ai | = 9 + 9 + 9 +
4 5 6 7
= 27 280.

Since Ai ∩ Aj = ∅ if i 6= j (there are only seven shifts), the principle of inclusion-

exclusion says that the value we want also equals
10
X
|E| − |Ai | = 107 − 10 · 27 280
i=1
= 9 727 200.
 (b) Same problem, but where the shifts are all regarded as the same (i.e.,
only the number of them matters.)?
Solution: Let’s do inclusion-exclusion again, but now we want to count the num-
ber of solutions to a1 + · · · + a10 = 7, where 0 ≤ ai ≤ 3 for each i, by letting ai
be the number of shifts that nurse i works. This is easy, because (again) no two
nurses can work more than three shifts each.

4. Write an exponential generating function for the number of words of length n

in the letters {a, b, c, d} in which the number of a’s and b’s combined is odd.
Can you find an explicit expression for the number of such words in terms of
n?
Solution: Let’s first write down a generating function f (t) for a string of an odd
number of a’s and b’s: there are 2n such strings of n is odd, and zero if n is even.
Then

f (t) = 21 t1 /1 + 23 t3 /3! + 25 t5 /5! + · · ·

1 2t
e − e−2t .


=
2
n
P
Let h(t) = n≥0 hn t /n! be the generating function we are looking for. By the
multiplicative principle for e.g.f.s, the number of words of length n in {a, b, c, d} with
an odd number of a and b’s is obtained by multiplying f (t) with generating functions
for the number of ways to choose n c’s, then n d’s. In each case, associated exponential
generating function is et , so h(t) = f (t)e2 t = 1/2(e4 t−1), and we can see hn = 1/2·4n
for n ≥ 1, and h0 = 1.

5.

6. (a) Find the permutation of {1, 2, . . . , 6} with inversion sequence (4, 3, 2, 1, 0, 0).
Solution: 543216.
(b) Write the ordinary generating function for the number of permutations
of [6] with length n.
Solution: Same as the number of solutions to a1 + a2 + a3 + a4 + a5 + a6 = n,
where 0 ≤ ai ≤ 6 − i. So that’s
6
Y 1 − xi
(1+x+x2 +· · ·+x5 )(1+x+x2 +· · ·+x4 )(1+x+x2 +x3 )(1+x+x2 )(1+x) = .
i=1
1−x

7. Find the ordinary generating function for the number of ways to make n cents
using at most four pennies and an unlimited supply of nickels and dimes. Use
this to decide the number of ways to make 1 dollar.
 Solution: Since a product of ordinary generating functions counts combinations, we
just need to multiply generating functions for the pennies, nickels, and dimes. The
generating function for at most four pennies is
1 − t5
1 + t + t2 + t3 + t4 = ,
1−t
while the generating function for the nickels (counted by value) is 1/(1 − t5 ), and
similarly 1/(1 − t10 ) for the dimes.
Multiplying, we get
1 − t5 1 1 1
= .
1 − t 1 − t5 1 − t10 (1 − t)(1 − t10 )
The number of ways to make one dollar is the coefficient of t100 . One way to find this
is just to multiply:
X X
(1 − t)−1 (1 − t10 )−1 = ( tn )( t10n ).
n≥0 n≥0

Look at the contribution from the right-hand factor. For each choice of n, 0 ≤ n ≤ 10,
there is exactly one way to choose a term from the left factor to get a t100 . Otherwise
there are none. So the number of ways to make 100 cents is 11.

8. Show that the number of partitions of size n with no repeated parts is equal
to the number of partitions with all parts of odd size. [Hint: compare o.g.f.’s]
Solution: The generating function for the number of partitions with no repeated parts
is Y
F (t) = (1 + tn ),
n≥1

by the product principle for ordinary generating functions. The generating function
for partitions with only odd parts is
Y
G(t) = (1 − t2n−1 )−1 ,
n≥1

by the same argument as we had to count all the partitions. We want to show that
F (t) = G(t). So multiply:
Y Y
F (t)G(t)−1 = (1 + tn ) (1 − t2n−1 )
n≥1 n≥1
Y 1 − t2n Y
= (1 − t2n−1 )
1 − tn
n≥1 n≥1
Y
2n
Y 1 1 Y
= 1−t · (1 − t2n−1 )
1 − t2n 1 − t2n−1
n≥1 n≥1 n≥1
= 1, since all terms cancel.
 (The third line is obtained by splitting up the denominator into terms with even and
odd powers of t.) So F (t) = G(t), as required.

9. Let fn be the number of ways to make a n-letter word from the letters X, Y, Z,
with the condition that every Y is followed immediately by a Z. Find an
expression for fn in terms of n. For practice, do this two ways: find an
ordinary generating function and compute. Check your work by finding a
recurrence relation satisfied by the fn ’s and solving it.
Solution: Since the expansion of 1/(1 − S) is the formal sum of permutations of the
multiset S, we can compute the ordinary generating function
X
F (t) = fn tn
n≥0

as follows. The goal is to count permutations of the multiset {∞ · X, ∞ · Y Z, ∞ · Z}.

Since X and Z have length 1 and Y Z has length 2, the ordinary generating function
is F (t) = 1/(1 − 2t − t2 ).
Alternatively, note that f0 = 1 and f1 = 2. To count the n-letter words, where n ≥ 2,
split them into two groups. Words that end in Y Z are in one-to-one correspondence
with with words of length n − 2 (just by adding a Y Z onto the end, which we can
always do.) So there are fn−2 words of this sort.
Words that don’t end in Y Z end in either X, or ZZ. In either case, we can remove
the last letter to get a word of length n − 1; conversely, any word of length n − 1 can
have a X or Z stuck on the end. So there are 2fn−1 words of this type.
It follows that, for n ≥
P 2, fn = 2fn−1 + fn−2 , and f0 = 1, f1 = 2. To solve the
recurrence, let F (t) = n≥0 fn tn . Then

F (t) = f0 + t(f1 − 2f0 ) + 2tF (t) + t2 F (t)

= 1 + 2tF (t) + t2 F (t)

so F (t) = 1/(1 − 2t − t2 ), as before.

√ √
Factor: 1 − 2t − t2 = (1 − (1 + 2)t)(1 − (1 − 2)t). Then, expanding by partial
fractions, √ √
(1/4)(2 − 2) (1/4)(2 + 2)
F (t) = √ + √ ,
1 − (1 + 2t) 1 − (1 − 2t)
so
1 √ √ 1 √ √
fn = (2 − 2)(1 + 2)n + (2 + 2)(1 − 2)n ,
4 4
for n ≥ 0.

10. Let gn be the number of ways to select a breakfast consisting of an odd number
of eggs, at most four pieces of toast, and at least one slice of bacon. Find an
 ordinary generating function for the sequence {gn } and use it to compute gn
in terms of n.
Solution: A breakfast is completely determined by integers a1 , a2 , and a3 , where
0 < a1 is odd, 0 ≤ a2 ≤ 4, and a3 ≥ 1. By the product principle for ordinary
generating functions,
X
gn tn = (t + t3 + t5 + · · · )(1 + t + t2 + t3 + t4 )(t + t2 + t3 + · · · )
n≥0

t 1 − t5 t
=
1 − t2 1 − t 1 − t
t2 (t + t2 + t3 + t4 + t5 )
=
(1 − t)2 (1 + t)
9t2 + 2t − 6
= 6 + 4t + 2t2 + t3 + by long division
(1 − t)2 (1 + t)
5 1 35 1 1 1
= 6 + 4t + 2t2 + t3 + · − · + ·
2 (1 − t)2 4 1−t 4 1+t
X∞
= 6 + 4t + 2t2 + t3 + 5/2(n + 1) − 35/4 + 1/4(−1)n )tn ,
n=0

from which we see gn = (10n − 45 + (−1)n )/4 for n ≥ 4, and g0 = g1 = 0, g2 = 1,

g3 = 2.

11. Show that the Stirling numbers satisfy, for each k ≥ 1, the generating function
identity
X tk
S(n, k)tn = .
(1 − t)(1 − 2t) · · · (1 − kt)
n≥0

12. How many different ways are there to label each face of a cube with an arrow
↑ , taking rotational symmetry into account? [Use Burnside’s Lemma.]
Solution: Let X be the set of labellings, without regard to symmetry, and let G be
the symmetries of the cube, permuting the elements of X. We need to compute the
number of labellings fixed by each symmetry in G.
• g = 1: every labelling is fixed by the identity permutation, of course. Each face
can be labelled in four ways, and there are six faces, so F1 = X and |X| = 46 .
• g a 90◦ rotation around a face axis: the arrow on a face that contains the axis
of symmetry can’t be sent to itself. So Fg = ∅. The same argument applies to
the 180◦ rotations around a face axis.
• If g is a vertex-rotation, recall g has two 3-cycles of faces that share a vertex.
If we choose an arrow for one of those faces, there is only one way to chose the
other two so that the arrows are sent to each other by the 120◦ rotation. There
are 2 three-cycles, so for each such g, we have |Fg | = 4 · 4.
 • if g is an edge-rotation, the faces fall into three two-cycles. For each, choosing
an arrow on one face determines the arrow for the other face. [Picture?] So
|Fg | = 43 .

Adding it all up, we find there are

1 X 1 6
4 + 8 · 42 + 6 · 43


|Fg | =
|G| 24
g∈G
= 192

distinct labellings.

13. Show that the exponential generating function for the number of derange-
ments,
∞
X
Dn tn /n!,
n=0

equals
e−t
,
1−t
if we agree D0 = 1. [For maximum nutritional value, try using the product
principle, or the recurrence relation Dn = (n − 1)(Dn−1 + Dn−2 ).]
n
P
Solution: The fastest way is remember that 1/(1 − t) = n≥0 n!t /n! is the ex-
ponential generating function for the number of permutations of length n. Let
d(t) = n≥0 Dn tn /n!.
P

Let’s count the permutations by noticing that every permutation has some subset
S of fixed points, and the restriction of the permutation to the remaining elements
[n] − S is a derangement. The number of ways to let a set S be the fixed points of a
permutation is just 1, for all k = |S| ≥ 0. The e.g.f. for the sequence (1, 1, 1, . . .) is
et .
By the product principle for exponential generating functions, every permutation
is obtained by putting a derangement on a subset and making the complementary
elements fixed points, so
1
et d(t) = .
1−t
That is, d(t) = e−t /(1 − t), as required.