# Tilings of 1*n rectangle.

The question: How many ways are there to tile a $$1*7$$ rectangle with tiles of size $$1*1,1*2,1*3$$.

My attempt: Now, the required recurrence would be: $$a_n=a_{n-1}+a_{n-2}+a_{n-3}$$ Where $$a_n$$ is the number of tilings if a $$1*n$$ rectangle. This is the general case, so I hoped to get the case where $$n=7$$ from this.

Using $$A(x)$$ as the Generating function for this recurrence, I end up with: $$A(x)= \frac 1 {1-x-x^2-x^3}$$.

I'll certainly find the answer for $$n=7$$ by using the recurrence directly. But if you help solve it for the general case, I'll be extremely happy and grateful.

How do I proceed further? Please answer as soon as possible. Thank you all!!!

• In your first display equation, the middle subscript should be $n-2$ Now you need to expand $A(x)$ in positive powers of $x$ and find the coefficient of $x^7$ – Ross Millikan Oct 5 '19 at 3:45
• You don't need the generating function, just use your recursion to find the the first few values of $a_n$ similar to how you find Fibonacci values. – Cheerful Parsnip Oct 5 '19 at 3:46
• Your question seems a bit muddled. You say you can use the recursion to solve $n=7$, but instead you want to solve the general case and then apply it to $n=7$? But why? Binet’s formula for Fibonacci numbers is already somewhat messy to evaluate, and this recurrence is cubic so it will look 5 times more uglier :). What’s the benefit? – Erick Wong Oct 5 '19 at 4:46
• Just wanted to see a closed form for this... It's the only wish in my life... – Sen47 Oct 5 '19 at 4:48
• @Sen47 In that case titling your question “Tilings of 1*7 rectangle” seems like a very indirect way of indicating your wish! – Erick Wong Oct 5 '19 at 4:53

For general case, you need to find the roots of this cubic equation $$\alpha,\beta,\gamma$$ using a computer or using this https://math.stackexchange.com/a/819749. Now, general formula for $$a_n$$ is $$a_n=A\alpha^n+B\beta^n+C\gamma^n$$ Now, use initial conditions $$a_1=1$$ $$a_2=2$$ $$a_3=4$$ to find coefficients $$A,B$$ and $$C$$ to proceed.
For this particular problem, just use this recursion again and again. $$a_7=a_6+a_5+a_4$$ $$=2a_5+2a_4+a_3$$ $$=4a_4+3a_3+2a_2$$ $$=7a_3+6a_2+4a_1$$ $$=28+12+4=44$$
• The coefficients of $a_i$ in your last two equations are wrong. For instance the $2a_5$ contributes $2a_2$ to the next now, not $a_2$. – Erick Wong Oct 6 '19 at 5:16