Do those problems, it’s not due May 1st, it’s due today(4/30) 3pm.
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 a
n.
(b) Find a simple expression for the generating function
∑
n≥0 anz
n as a quotient of two
polyno
mials.
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
∑
n≥0 anz
n.
3. Let an = 5 · 3n − 2n+1 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 z100 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
∑
n≥1 nz
n as a quotient of two polyno-
mials.