数学：使用一个堆栈查找排列数

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 排列中选择 code>14.. 有谁知道任何函数 F(n) 可以产生堆栈（只有一个）可以产生的排列数量？例如 f(1)=1

f(2)=2

f(4)=14

Answer 1

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

Answer 2

我认为有一些非常简单的公式。您正在寻找 N 压入操作（“X”）和 N 弹出操作（“Y”）操作的排列，遵循一个简单的规则：

• 空堆栈上不弹出操作（fe Y.... 和 XXYYY... 无效）

也许一些递归定义有帮助：

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;
}