Combinatorics and applications Problems
Sooooooft
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 ∑
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
∑ 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.