Results 1 to 2 of 2

Math Help - Catalan numbers and tiling

  1. #1
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Catalan numbers and tiling

    Proove that Cn(Cataln number) is the number of ways to tile a stairstep shape of height n with n rectangles.
    Last edited by mr fantastic; January 3rd 2010 at 11:03 PM. Reason: Changed post title
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Apr 2008
    Posts
    191
    Quote Originally Posted by Also sprach Zarathustra View Post
    Proove that Cn(Cataln number) is the number of ways to tile a stairstep shape of height n with n rectangles.
    If you actually draw your staircase going up from left to right, then the rectangle in the lower right hand corner is special. For a particular staircase of height n+1, this rectangle separates the staircase into two smaller staircases of heights "j" and "n-j". And "j" ranges from 0 to n. This fact can help you set up a recurrence relation, the solution of which is the Catalan numbers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Approximation for large Catalan Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 14th 2010, 08:30 AM
  2. Catalan's Constant
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: August 11th 2010, 09:16 PM
  3. Domino Tiling
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 24th 2008, 04:02 PM
  4. Catalan Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 11th 2008, 08:51 AM
  5. Catalan Numbers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 1st 2008, 05:38 AM

Search Tags


/mathhelpforum @mathhelpforum