Student: Stanley

# 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 Pn 0 anzn as a quotient of two polynomials.
2. Consider the recurrence an = 3an 1 4an 3, with initial conditions a0 = 1, a1 = 2, a2 = 6.
expression for the generating function a zn.
3. Find a simple 3 n 2 n+1 for n 0. Find a simple Pn 0 n
Let an = 5 expression for the generating function
Pn 0 anzn as a quotient of two polynomials.
4. Find a generating function A(z) such that the coe cient 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 Pn 1 nzn as a quotient of two polyno-mials.

**Budget: ** $10.00

** Due on: **April 30, 2020 00:00

** Posted: ** 6 months ago.

#### Answers (0)