Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Suppose I have a stack and I want to find the permutations of numbers 1,2,3,...n.

I can push and pop. e.g. if n=2: push,pop,push,pop 1,2 and push,push,pop,pop 2,1

if n=4 I can only get 14 from the 24 permutations using the stack.. Does anyone know any function F(n) that could produce the number of permutations the stack (only one) can produce? eg f(1)=1



Thank you

share|cite|improve this question

The number corresponds to the Catalan Numbers which are of the form $\displaystyle \frac{{2n \choose n}}{n+1}$.

I believe this particular problem is an exercise Knuth's Art of Programming Volume I.

For a hint of proof: Number of pushes $\ge$ Number of pops in any prefix of the string of pushes and pops.

share|cite|improve this answer
Thank you very much! – alhid Jan 16 '11 at 21:26

Your Answer


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