背景

卡特兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡特兰（1814–1894）命名。历史上，清朝数学家明安图（1692年－1763年）在其《割圜密率捷法》中最先发明这种计数方式，远远早于卡特兰。有中国学者建议将此数命名为“明安图数”
或“明安图-卡特兰数”。-- by Wikipedia
其一般公式为:
卡特兰数

问题

n个不同元素依次入栈,问有多少种合法的出栈顺序?

思路

有A、B两个元素,入栈顺序AB,则出栈情况有两种:

  1. 入A, 出A, 入B, 出B.
  2. 入A, 入B, 出B, 出A.

现在假设f(n)为 " n 个不同元素依次入栈, 出栈顺序的种类数". 显然f(1)=1,f(2)=2.
现在按照第一个入栈元素,在出栈序列中的位置进行分类讨论, 假设入栈序列ABCD:

  1. A第一个出栈时,A先进,然后马上出栈.这种情况下,共有“BCD出栈顺序的种类数”种方案.也就是f(n-1)种.
  2. A第二个出栈时,A先进,B再进,之后B需要马上出来(这样才能确保A排第二),此时共有f(n-2)种方案.
  3. A第三个出栈时,A先进,之后只要确保排在A后面两个的元素比A先出即可.此时共有f(2)*f(n-3)种方案.f(2)是指“BC入栈出栈顺序的种类数”,f(n-3)是指”D入栈出栈的种类数”.
  4. A第四个出栈时,A先进,只需确保排在A后面的三个元素比A先出即可,即f(n-1)种.

此时可得:

上式中,f(0)=1.
这个实际上就是卡特兰数的递推式:

其通项公式即:

也可以表示为:

所以元素A、B、C、D依次进栈,其所有可能的出栈序列,应该有14种情况
A第一个出栈：ABCD;ACBD;ACDB;ABDC;ADCB;
A第二个出栈：BACD;BADC;
A第三个出栈：CBAD;BCAD;
A第四个出栈：BCDA;CBDA;CDBA;BDCA;DCBA.

参考

🔗卡塔兰数-维基百科🔗
🔗n个数依次入栈，出栈顺序有多少种？🔗