Results 1 to 2 of 2

Math Help - recurrences

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    5

    recurrences

    Suppose you have large collections of red 1 * 2 tiles, blue 1 * 2 tiles
    and green 1 * 2 tiles. For n >= 0, let tn be the number of ways to use
    these to (exactly) cover the squares of a 2 * n checkerboard (i.e., without
    overlapping of tiles). Note that tiles can be placed on the board either
    vertically or horizontally.

    (a) Determine t0, t1, t2 and t3.

    (b) Find a recurrence relation and initial conditions for tn.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    A couple of tips:

    Given a 2 * n checkerboard,

    1. you must use n tiles to cover it, each of which has 3 possible colors.

    2. two horizontal tiles can be exchanged for two vertical tiles for a different configuration.

    3. all possible configurations (without respect to color) can be obtained by starting with a configuration of all horizontal tiles and making exchanges of two horizontal tiles for two vertical tiles.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solve the following linear recurrences.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 13th 2011, 02:01 AM
  2. Solve the following linear recurrences.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 12th 2011, 07:21 PM
  3. Recursion Trees with Recurrences
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 30th 2010, 05:20 PM
  4. recurrences
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 26th 2008, 11:29 AM
  5. recurrences
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 10th 2007, 11:32 PM

Search Tags


/mathhelpforum @mathhelpforum