Thread: 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.

Originally Posted by Also sprach Zarathustra

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.