# How many ways to climb up a staircase

Given a checkerboard size nxn, counting the number of ways we can get from one corner to another corner diagonally across by only going upwards and to the side (unidirectionally) can be computed by treating the two directions, up and side as objects to be permuted. The number of ways to get to the corner is thus the number of arrangements that can be made of these two sets of n objects each.

The number of ways we can arrange is computed by fixing one object(up), and considering that there are n+1 'SLOTS' between them to insert the other object(sideways) giving us n(n+1) ways to move from one corner to the other.

Now my question is suppose that the checkerboard is split in half diagonally across, giving something which looks like a staircase, how many ways are there to move up? (I.e. how many arrangments are there such that at any point the number of 'side' thus not exceed the number of 'ups' preceding it?)

Does this problem require partition theory?

-
There is considerable literature on this, which you can find by searching for "ballot numbers" or "the ballot problem" (it's the number of ways of counting the ballots in a tied election so one of the candidates is never ahead). –  Gerry Myerson Feb 1 '13 at 11:44
See also the discussion at math.stackexchange.com/questions/165856/… –  Gerry Myerson Feb 1 '13 at 11:47
This is one ofthe many many problems whose solution is given by the Catalan numbers. There is no particularly direct relation with partition theory. –  Marc van Leeuwen Feb 1 '13 at 15:31
The Wikipedia article on Catalan numbers has a fairly decent discussion of exactly this application of them. –  Brian M. Scott Feb 1 '13 at 19:36