2
$\begingroup$

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!!!

$\endgroup$
8
  • $\begingroup$ 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$ $\endgroup$ – Ross Millikan Oct 5 '19 at 3:45
  • 2
    $\begingroup$ 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. $\endgroup$ – Cheerful Parsnip Oct 5 '19 at 3:46
  • $\begingroup$ 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? $\endgroup$ – Erick Wong Oct 5 '19 at 4:46
  • $\begingroup$ Just wanted to see a closed form for this... It's the only wish in my life... $\endgroup$ – Sen47 Oct 5 '19 at 4:48
  • $\begingroup$ @Sen47 In that case titling your question “Tilings of 1*7 rectangle” seems like a very indirect way of indicating your wish! $\endgroup$ – Erick Wong Oct 5 '19 at 4:53
2
$\begingroup$

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$$

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ – Erick Wong Oct 6 '19 at 5:16
  • $\begingroup$ @ErickWong, yeah, corrected now. Thanks $\endgroup$ – Martund Oct 6 '19 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.