栈|Catalan函数

选择题里常考的一类题,将其依次入栈,中间可以出栈,问可以形成多少种出栈序列?

$$
\frac{1}{n+1}C_{2n}^{n}
$$

引例

假设入栈的顺序为a,b,c

则有以下几种情况:

  1. a⬇,a⬆,b⬇,b⬆,c⬇,c⬆:abc
  2. a⬇,a⬆,b⬇,c⬇,c⬆,b⬆: acb
  3. a,b,c,c,b,a: cba
  4. a,b,b,a,c,c: bac
  5. a,b,b,c,c,a: bca

证明

  1. 对于栈而言,存在(入栈)和(出栈)两种操作;

  2. 总的出栈次数等于入栈次数,操作总次数为2n,这样栈才能空;

  3. 2n次中,n次入栈,n次出栈,即存在 $C_{2n}^{n}$ 种分配方式

  4. $C_{2n}^{n}$ 种分配方式中,任何一次出栈时,入栈的次数应该大于等于出栈的次数,否则栈空时出栈违法;

  5. $C_{2n}^{n}$ - 非法操作 = 合法操作;

  6. 非法操作:某次出栈时,出栈次数大于入栈次数;

  7. 坐标轴表示

    image-20220729164416113

  8. 非法的操作肯定会与y=-1有一个交点,最后还是会回到0;

  9. 将所有非法操作关于y=-1进行折叠变换,终点为(2n,-2);

  10. 不合法的操作次数:入栈比出栈少两次,入栈为n-1次,出栈为n+1次;

  11. 不合法的操作序列数为$C_{2n}^{n-1}$;

  12. 合法操作数用$C_{2n}^{n}$-$C_{2n}^{n-1}$即可获得$\frac{1}{n+1}C_{2n}^{n}$。

后期二叉树还会接触。