how this recurrence relation came f(n)=f(n-4)+f(n-1)
Tiling problem recurrence
Hey @shampblocks,
The size of the tile is 4x1 i.e. 4 rows and 1 column.
You can place the tile in two ways:
- vertically(1 tile of 4x1): it will occupy 1 column leading to f(n-1)
- horizontally(4 tiles of 1x4): it will occupy 4 columns leading to f(n-4)
f(n): when you have n columns to cover
f(n-1): now you have only n-1 columns to tile
f(n-4): now you have only n-4 columns to tile.
Hope, this would help.
Give a like if you are satisfied.
1 Like
can you tell my code is right?
ohk thanks sir…
and one more doubt sir if the brick is of dimension 2 by 1 instead 4 by 1 then how to solve it
and wall dimension become 5 by n??
Hello @shampblocks ,
In that case,
You might not be able to cover the area completely for n being odd.
In the question, you have provided.
There are two ways of placing tiles:
- 4 tiles of 2x1 and one tile of 1x2
- 5 tiles of 1x2.
So, each time 2 columns are being covered.
What will be recurrence relation??
Hello @shampblocks,
As i have said that it will for odd value of n.
So, the recurrance relation for tilling 4xn with 2x1 tiles is:
f(n)=f(n−1)+5*f(n−2)+f(n−3)−f(n−4)
Explanation:
There are eight ways in which a 4×n tiling can begin, shown and named in the picture below. We’ll count the number with each kind of beginning configuration and add the results up to get f(n).
Types A through E are easy. Any 4×(n−1) tiling can extend A to give a 4×n tiling, and there are no other ways to get a “type A” 4×n tiling. So there are f(n−1) “type A” 4×n tilings. Similarly, there are f(n−2) type B 4×n tilings, and f(n−2) as well of each of the types C, D, and E. That’s f(n−1)+4f(n−2) so far.
Tilings with starting configurations F, G, and H are a little harder to count. First define some helpful notation.
Let fT(k) represent the number of 4×k tilings of type T, where T is a set of starting configurations. That lets us say from what we have above that
f(n)=f(n−1)+4f(n−2)+f{F,G,H}(n).
We just have to figure out f{F,G,H}(n) in terms of f.
Clearly f{F,G,H}(n)=f{F}(n)+f{G}(n)+f{H}(n); we’ll compute each term separately. Also take note of the fact that f(k)=f{A,B,C,D,E,F,G,H}(k).
Now on to the counting. We’ll look at type F first.
A “type F” 4×(n) tiling is always configuration F extended by a “type B” or “type F” 4×(n−2) tiling that has its center left domino removed. So fF(n) is exactly the number of 4×(n−2) “type B” or “type F” tilings, that is, fF(n)=f{B,F}(n−2). (The type B and F tilings are exactly the ones that have a center left domino to remove.)
A “type G” tiling is G extended by a tiling of type A, C, or G, with the lower left domino removed, so fG(n)=f{A,C,G}(n−2). (A, C, and G are the tiling types with a lower left domino.)
A “type H” tiling is H extended by a tiling of type A, D, or H, with the upper left domino removed. So fH(n)=f{A,D,H}(n−2). (A, D, and H are the tiling with an upper left domino.)
Substituting these last three expressions into the previous displayed equation yields
f(n)=f(n−1)+4f(n−2)+f{B,F}(n−2)+f{A,D,H}(n−2)+f{A,C,G}(n−2)
=f(n−1)+4f(n−2)+f{A,B,C,D,F,G,H}(n−2)+f{A}(n−2)
=f(n−1)+4f(n−2)+f(n−2)−f{E}(n−2)+f{A}(n−2)
=f(n−1)+5f(n−2)+f{A}(n−2)−f{E}(n−2)
Fortunately, A and E are the simplest patterns, and we know from our initial calculations (which we did before adopting the subscript notation on f) that f{A}(n−2)=f(n−3) and f{E}(n−2)=f(n−4). These final calculations give the recurrence relation you asked about:
f(n)=f(n−1)+5f(n−2)+f(n−3)−f(n−4).
I’ll let someone else suggest good references for learning these techniques and just say experience helps. The hundredth one is a lot quicker to figure out than the first one!
Hope, this would help.
Give a like if you are satisfied.
1 Like
How to think in these questions I cannot able to find recurrence… Any suggestion you want to give…
Practice @shampblocks,
The more you would practice such kind of questions, the more thinking ability will enhance.
Just think for all the possible cases.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.