Maths: Find permutation number using one stack

It's more a math problem I guess, nothing programming.

Suppose开发者_如何学C 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

f(2)=2

f(4)=14

Such function is a Catalan number. See http://en.wikipedia.org/wiki/Catalan_number for the formula.

I think there is some quite easy formula for that. You're looking for permutations of N push operations ("X") and N pop ("Y") operations, following one simple rule:

• No pop on an empty stack (f.e. Y.... and XXYYY... are invalid)

Perhaps some recursive definition helps:

function F(n_push, n_pop) {
  int total_count = 0;

  if (n_push > 0) total_count += F(n_push - 1, n_pop);
  if (n_pop > n_push) total_count += F(n_push, n_pop - 1);

  return total_count;
}