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