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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Stairstep Interpretation Catalan Date
A Interpreting a paper on spectral analysis Wednesday at 3:05 PM
A Interpreting Chi Squared ... backward Feb 11, 2018
I Interpreting the correlation Feb 6, 2018
I Bayes again - how to interpret in vitro genotoxicity data Jun 10, 2017
Relation between Catalan numbers Oct 22, 2007