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.