Proove thatCn(Cataln number) is the number of ways to tile a stairstep shape of heightnwithnrectangles.

Printable View

- Dec 24th 2009, 04:26 PMAlso sprach ZarathustraCatalan numbers and tiling
Proove that

*C**n*(Cataln number) is the number of ways to tile a stairstep shape of height*n*with*n*rectangles. - Jan 21st 2010, 10:50 PMRoam
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.