function - 数学 : Find permutation number using one stack

Question

我猜这更像是一个数学问题，而不是编程。

假设我有一个堆栈，并且我想找到数字1,2,3,...n的排列。我可以push和pop。例如如果 n=2:push,pop,push,pop 1,2 和 push,push,pop,pop 2,1

如果 n=4，我只能使用 stack 从 24 排列中获得 14。有谁知道任何函数 F(n) 可以产生堆栈(只有一个)可以产生的排列数量？例如f(1)=1

f(2)=2

f(4)=14

Answer 1

这样的函数是一个加泰罗尼亚数。请参阅http://en.wikipedia.org/wiki/Catalan_number求公式。