Combinatorics and applications Problems

profileSooooooft
gec2020hw3.pdf

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.