Combinatorics and applications Problem Set 3

Combinatorics and applications
Problem Set 3
1. Let an be the number of ways to tile a 1 × n board with 1 × 1 squares, 1 × 2 rectangles, and
1 × 3 rectangles.
(a) Find a recurrence for an.
(b) Find a simple expression for the generating function P
n≥0
anz
n as a quotient of two
polynomials.
2. Consider the recurrence an = 3an−1 − 4an−3, with initial conditions a0 = 1, a1 = 2, a2 = 6.
Find a simple expression for the generating function P
n≥0
anz
n
.
3. Let an = 5 · 3
n − 2
n+1
P
for n ≥ 0. Find a simple expression for the generating function
n≥0
anz
n as a quotient of two polynomials.
4. Find a generating function A(z) such that the coefficient of z
100 is the number of ways to
give change of a dollar (that is, 100 cents) using cents, nickels (5-cent coins), dimes (10-cent
coins), and quarters (25 cent coins).
5. Find a simple expression for the generating function P
n≥1 nzn as a quotient of two polynomials.