卡特兰数-Catalan number

问题

栈是一种先进后出(FILO,First In Last Out)的数据结构。当栈的进栈顺序为$1,2,3,…,n$ 时,问有多少种不同的出栈序列?


分析

设$C(n)​$是$n​$个数所有合法出栈序列的个数。

思路1:递归

以某个基准数在出栈序列中的顺序来讨论,基准数用$k$表示。$C(n)$可以分解为:

  • $k​$在最后一个位置。那么$k​$先进栈,最后出栈;其他$n-1​$个元素$12,k-1,k+1…,n​$(共$n-1​$个元素)的出栈个数为$C(n-1)​$
  • $k$在倒数第二个位置。那么有一个元素比$k$先进栈,共$C(1)$种可能;其他$n-2$个元素的出栈个数为$C(n-2)$。由组合数的乘法原理,得到总的出栈个数为$C(1)*C(n-2)$
  • $\cdots$
  • $k$在第一个位置。那么$k$先进栈,然后马上出栈;其他$n-1$个元素的出栈个数为$C(n-1)$。总的出栈个数为$C(n-1)$。

令$C(0)=1​$,从有

参考母函数推卡特兰数通项公式note1,可得

思路2:排列组合

用$+1$表示进栈,$-1$表示出栈。那么出栈序列$3,2,1$(假设序列为$1,2,3$)的进出栈顺序为

对于$n$个数的序列,共有$n$次进栈($+1$)和$n$次出栈$-1$.

对$+1,-1$这$2n$个数字,对其做排列,我们的目标是找到所有合法的排列(对应合法的出栈顺序)。

  1. 总的排列个数为$\begin{pmatrix}
    2n \\
    n
    \end{pmatrix}$

  2. 不合法的个数

    不合的排列一定会出现这种情况:从左往右若干项和为$-1$, 该项一定在奇数位置。

    共$n$个$+1$,$n$个$-1​$

    构造映射:将前$2i+1$项取反(第$2i+1$项为首次出现累加和为$-1$的位置), 结果为

    共$n+1$个$+1$, $n-1$个$-1$

    该映射为一一映射,所以不合法个数与 共$n+1$个$+1$, $n-1$个$-1$的全排列个数一样,即,$\begin{pmatrix}
    2n \\
    n+1
    \end{pmatrix}$或者$\begin{pmatrix}
    2n \\
    n-1
    \end{pmatrix}$.

经过简单的计算,有


一些类似的问题

合法括号表达式个数

计算$n$对括号形成的合法括号表达式的个数。

合法:$(())(), ()()$

不合法:$((), ())))$

分析:将$($看做进栈,将$)​$看做出栈。

答案

电影购票

电影票每张50元,如果有$m+n​$个人排队买票,其中$m​$个人各持有50元面值的钞票1张,另外$n(n\le m)​$个人各持有100元面值的钞票1张,而票房没有预备找零.有多少种方法可以将这$m+n​$个人排成一列,顺序购票,使得无需因为等待找零而耽误时间?

分析:当手持100元的人买票时,前面至少有一个手持50元的人已经买过票了。把手持50元的人买票看做进栈, 用$+1$表示。把手持100元的人买票看做出栈, 用$-1$表示。从而转化为求解合法出栈方式的问题(当$m=n$时,栈最终为空;当$m>n$时,栈内留下$m-n$个元素。)

答案:

街区对角线问题

有一个$n\times n$的网格,需要从左下角走到右上角,每一步均为向上或向右。求不越过对角线的单调路径的个数。

分析:从左下角走到右上角,总的步数为$2n$步,其中$n$步向右,$n$步向上。不穿过对角线的走法需要向右走的步数大于等于向上走的步数。将向右看做入栈,用$+1$表示;将向上看做出栈,用$-1$表示。则可以转化为合法出栈方法个数的问题。

答案note2

参考





note1. 错误修改: $\lim_{x\rightarrow 0^+} \frac{1-\sqrt{1-4x}}{2x} =\lim_{x\rightarrow 0^+} \frac{1}{\sqrt{1-4x}}= 1$ 和 $\lim_{x\rightarrow 0^+} \frac{1+\sqrt{1-4x}}{2x} = + \infty $.
note2. 不过对角线的走法,也可以从左上部分走。走法要求向上的次数大于等于向右的次数。条数与从对角线下方走一样,所以答案为$2C(n)$。参考http://www.cnblogs.com/wuyuegb2312/p/3016878.html