# Find a generating function involving a tiling problem. Let hn be the number of ways to tile a 1 times n rectangle with 1 times 1 tiles that are red or blue and 1 times 2 tiles that are green, yellow, or white. Find a closed formula for H(x)=sum_{n >= 0} h_n x^n

Francisco Proctor 2022-07-18 Answered
Find a generating function involving a tiling problem
Let ${h}_{n}$ be the number of ways to tile a $1×n$ rectangle with $1×1$ tiles that are red or blue and $1×2$ tiles that are green, yellow, or white. Find a closed formula for $H\left(x\right)=\sum _{n\ge 0}{h}_{n}{x}^{n}.$
I am unsure how to start this problem. Is there a way to solve this without using recurrence relations?
You can still ask an expert for help

## Want to know more about Discrete math?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

penangrl
Step 1
A recurrence relation is a good place to start. By considering the possibilities for the first tile, we obtain ${h}_{n}=2{h}_{n-1}+3{h}_{n-2}$ for $n\ge 2$. The boundary conditions are ${h}_{0}=1$ and ${h}_{1}=2$.
Step 2
Now the recurrence relation and boundary conditions yield $H\left(x\right)-1-2x=2x\left(H\left(x\right)-1\right)+3{x}^{2}H\left(x\right),$ from which we find that $H\left(x\right)=\frac{1}{1-2x-3{x}^{2}}.$.
Partial fraction decomposition then yields $H\left(x\right)=\frac{1/4}{1+x}+\frac{3/4}{1-3x},$, which immediately implies the explicit formula
${h}_{n}=\frac{1}{4}\left(-1{\right)}^{n}+\frac{3}{4}\cdot {3}^{n}=\frac{\left(-1{\right)}^{n}+{3}^{n+1}}{4}.$
###### Not exactly what you’re looking for?
Marcelo Mullins
Step 1
In general, if you want the generating function for the number of sequences of objects with a total "weight" of n, where each entry is taken independently from a set of ${a}_{1}$ objects of weight one, and ${a}_{2}$ objects of weight two, etc, then the answer is
$\frac{1}{1-\left({a}_{1}x+{a}_{2}{x}^{2}+\dots \right)}=1+\underset{\text{sequences of one object}}{\underset{⏟}{\left({a}_{1}x+{a}_{2}{x}^{2}+\dots \right)}}+\underset{\text{sequences of two objects}}{\underset{⏟}{\left({a}_{1}x+{a}_{2}{x}^{2}+\dots {\right)}^{2}}}+\dots$
Step 2
In this case, you are counting sequences of tiles, where the weight of a tile is its area, and you want the generating function for tilings of weight n. There are two tiles with weight 1 (two squares), and three tiles of weight 2, so the answer is $1/\left(1-\left(2x+3{x}^{2}\right)\right)$