Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Stairstep Interpretation of Catalan Numbers

  1. Jan 1, 2010 #1
    How does one go about proving that [tex]C_n[/tex] (Catalan number) is the number of ways to tile a stairstep shape of height n with n rectangles? :rolleyes:
  2. jcsd
  3. Jan 12, 2010 #2
    If you 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. j ranges from 0 to n. This fact can help you set up a recurrence relation, the solution of which is the Catalan numbers.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook