数论基础-卡特兰数应用

已知进栈顺序固定为a、b、c三个元素，允许任意时刻出栈（栈操作合法），一共可以得到多少种不同的出栈序列？
若3个元素按1、2、3的顺序依次入栈，入栈过程中栈非空时可随时出栈，则合法的不同出栈序列总共有多少种？
现有1、2、3、4共4个元素按从小到大顺序依次入栈，入栈过程中可随时出栈，请问合法的出栈序列总共有多少种？
以下场景的计数结果，对应第n个卡特兰数（$C_n = \frac{1}{n+1} \binom{2n}{n}$）的是？
若有6个元素按1、2、3、4、5、6的顺序依次进栈，进栈过程中允许已入栈的元素随时出栈，则合法的出栈序列总共有多少种？
若入栈序列为1、2、3、4、5（入栈过程可随时出栈），则合法的出栈序列总数量为多少？
若入栈序列为1、2、3、4、5（入栈过程中可随时出栈），则所有合法的出栈序列总数量为多少？
3个不同元素按固定顺序入栈，允许任意时刻出栈，总共有多少种合法的出栈序列？
若1、2、3、4按顺序进栈，允许栈非空时任意时刻出栈，则合法的出栈序列总共有多少种？
若6个元素按1、2、3、4、5、6的顺序依次进栈，出栈操作可在任意合法时刻进行，请问总共有多少种不同的合法出栈序列？