- #1
BrownianMan
- 134
- 0
[tex]\textup{A 2 x 7 rectangle has tiling with 1 x 1 and 1 x 2 tiles (singletons and doubletons).}[/tex]
[tex]\textup{How many such tilings of a 2 x 7 grid are there?}[/tex]
[tex]\textup{Let }a_{n}\textup{ be the number of tilings of a 2 x n grid using 1 x 1 and 1 x 2 tiles so that the}[/tex]
[tex]\textup{two rightmost squares are occupied by singletons, let }b_{n}\textup{ be the number of tilings}[/tex]
[tex]\textup{ with one singleton and one doubleton in the rightmost squares, and let }c_{n}\textup{ be the}[/tex]
[tex]\textup{ number of other tilings (two horizontal doubletons or one vertical doubleton). The}[/tex]
[tex]\textup{problem asks for }a_{7}+b_{7}+c_{7}. \textup{ When one appends another column to the right side,}[/tex]
[tex]\textup{forming a 2 x (n + 1) grid, either one can add 2 singletons or a vertical doubleton, or}[/tex]
[tex]\textup{one can change any singletons in the nth column to doubletons. This yields:}[/tex]
[tex]a_{n+1}=a_{n}+b_{n}+c_{n}[/tex]
[tex]b_{n+1}=2a_{n}+b_{n}[/tex]
[tex]c_{n+1}=2a_{n}+b_{n}+c_{n}[/tex]
***doubletons may be placed vertically or horizontally.
Use the recurrence relations to obtain a numerical answer to the problem.
Not sure how do start this. Any help?
[tex]\textup{How many such tilings of a 2 x 7 grid are there?}[/tex]
[tex]\textup{Let }a_{n}\textup{ be the number of tilings of a 2 x n grid using 1 x 1 and 1 x 2 tiles so that the}[/tex]
[tex]\textup{two rightmost squares are occupied by singletons, let }b_{n}\textup{ be the number of tilings}[/tex]
[tex]\textup{ with one singleton and one doubleton in the rightmost squares, and let }c_{n}\textup{ be the}[/tex]
[tex]\textup{ number of other tilings (two horizontal doubletons or one vertical doubleton). The}[/tex]
[tex]\textup{problem asks for }a_{7}+b_{7}+c_{7}. \textup{ When one appends another column to the right side,}[/tex]
[tex]\textup{forming a 2 x (n + 1) grid, either one can add 2 singletons or a vertical doubleton, or}[/tex]
[tex]\textup{one can change any singletons in the nth column to doubletons. This yields:}[/tex]
[tex]a_{n+1}=a_{n}+b_{n}+c_{n}[/tex]
[tex]b_{n+1}=2a_{n}+b_{n}[/tex]
[tex]c_{n+1}=2a_{n}+b_{n}+c_{n}[/tex]
***doubletons may be placed vertically or horizontally.
Use the recurrence relations to obtain a numerical answer to the problem.
Not sure how do start this. Any help?