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

Question

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

假设我有 astack并且我想找到permutationsnumbers 1,2,3,...n。我可以push和pop。例如，如果 n=2：push,pop,push,pop1,2 和push,push,pop,pop2,1

如果 n=4 我只能14从24使用 .. 的排列中得到stack。有谁知道任何function F(n)可以产生permutations堆栈数量（只有一个）可以产生的东西？例如 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;
}