# Stairstep Interpretation of Catalan Numbers

1. Jan 1, 2010

### 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?

2. Jan 12, 2010

### 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.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook