Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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… – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.