Results 1 to 7 of 7

Math Help - Number of Ways

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    18

    Number of Ways

    Find the number of ways of tiling a "2 x n" rectangle with "1 x 2" and "2 x 2" tiles, given that the edges of the tiles are parallel to those of the rectangle.

    I have tried listing ways but that was only working through examples (2 x 1 rectangle, 2 x 2 rectangle, 2 x 3, 2 x 4 and so on, but the number increases very quickly and starts getting quite confusing. It also doesn't solve how many possibilities for n assumably in terms of n. How do i solve this showing working where possible??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,102
    Thanks
    68
    Hard to tell what's allowed:
    as example, in a 2 by 2 rectangle, can you have these 5 ways:
    1 2by2, or
    2 1by2 placed horizontally, or
    2 1by2 placed vertically ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    643
    Hello, cedricc!

    Find the number of ways of tiling a 2 \times n rectangle with 1 \times 2 and 2 \times 2 tiles,
    given that the edges of the tiles are parallel to those of the rectangle.

    I have tried listing ways but that was only working through examples
    (2 x 1 rectangle, 2 x 2 rectangle, 2 x 3 rectangle, so on),
    but the number increases very quickly and starts getting quite confusing.
    It also doesn't solve how many possibilities in terms of n.

    How do i solve this, showing working where possible?
    There is nothing wrong with Listing the cases and looking for a pattern.
    Quite often, it is the only approach available to us.


    I found this list . . .

    . . \begin{array}{cc}<br />
\text{Size} & \text{Tilings} \\ \hline<br />
2\times 1 & 1 \\<br />
2\times 2 & 3 \\<br />
2\times 3 & 5 \\<br />
2\times 4 & 9 \\<br />
2 \times 5 & 15 \\<br />
2\times 6 & 25 \\<br />
2\times 7 & 41 \\<br />
\vdots & \vdots \end{array}


    I see this pattern: Starting with the third term,
    . . each number is the sum of the preceding two numbers, plus 1.

    That is: . a_n \;=\;a_{n-1} + a_{n-2} + 1



    That's as far as I dare to go . . .
    .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,102
    Thanks
    68
    The On-Line Encyclopedia of Integer Sequences

    Enter A001595 in search box
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2010
    Posts
    18
    Quote Originally Posted by Soroban View Post
    Hello, cedricc!

    There is nothing wrong with Listing the cases and looking for a pattern.
    Quite often, it is the only approach available to us.


    I found this list . . .

    . . \begin{array}{cc}<br />
\text{Size} & \text{Tilings} \\ \hline<br />
2\times 1 & 1 \\<br />
2\times 2 & 3 \\<br />
2\times 3 & 5 \\<br />
2\times 4 & 9 \\<br />
2 \times 5 & 15 \\<br />
2\times 6 & 25 \\<br />
2\times 7 & 41 \\<br />
\vdots & \vdots \end{array}


    I see this pattern: Starting with the third term,
    . . each number is the sum of the preceding two numbers, plus 1.

    That is: . a_n \;=\;a_{n-1} + a_{n-2} + 1



    That's as far as I dare to go . . .
    .



    Considering, what "Wilmer" wrote, doesn't that mean there's more than three possibilities for a 2 by 2??
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,102
    Thanks
    68
    Whoops: I show 3 possibilities; my "5" is a typo; I'll repost:

    as example, in a 2 by 2 rectangle, you can have these 3 ways:
    1: one 2by2, or
    2: two 1by2's placed horizontally, or
    3: two 1by2's placed vertically

    Soroban's is CORRECT
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2010
    Posts
    18
    I see, thank you so much
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of ways
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 17th 2010, 11:58 PM
  2. Replies: 4
    Last Post: April 10th 2009, 02:03 PM
  3. Replies: 10
    Last Post: April 8th 2009, 11:56 AM
  4. number of ways
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2008, 06:52 AM
  5. number of ways
    Posted in the Statistics Forum
    Replies: 2
    Last Post: April 19th 2008, 02:54 PM

Search Tags


/mathhelpforum @mathhelpforum