Stairstep Interpretation of Catalan Numbers

[roam]

How does one go about proving that C_n (Catalan number) is the number of ways to tile a stairstep shape of height n with n rectangles? :rolleyes:

[techmologist]

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.