阅前提示
卡特兰数会用 会背就行
参考文章

1.n个元素进求出栈序列数推导

n 个元素进栈序列为：1，2，3，4，…，n，则有多少种出栈序列。
我们设入栈操作为1 出栈操作为-1
那么整个入栈出栈的操作就是一个 1 -1组成的序列 其中1与-1数量相同 且等于元素个数n
那么利用组合数学的知识就可以知道
$$\textbf{合法的序列个数=总序列个数-非法序列个数}$$

$\textbf{总序列个数}$=2n个位置放n个1和-1=$C_{2n}^n$

非法序列有多少个呢 我们先来看看非法序列的定义
非法序列个数就是-1在某一位时比1多 即栈为空了还有出栈操作
比如1 -1 -1 1这显然非法
从前缀和的角度来看 合法序列的前缀和无论哪一位都>=0
而非法序列的前缀和必然有一位是=-1的
那么将第一位到第一个前缀和为-1的那一位取反后面的不管 比如从 非法序列A1 -1 -1 1 变成 序列B-1 1 1 1
我们发现 去取反后变为了有n-1个-1 n个1的序列而且 因为是只对将第一位到第一个前缀和-1的那一位取反
所以后面的序列不受影响 意味着总体上无论n多大 我们都变少了一个-1变多了一个1
如果我们能证明每一个序列B都对应一个非法序列A 那么我们就知道了非法序列的个数
证明可见参考文章
因此非法序列A个数=序列B个数 序列B就是2n个位置放n-1个-1所以就是$C_{2n}^{n-1}$
$$\textbf{合法的序列个数=总序列个数-非法序列个数}$$
$\textbf{总序列个数}=C_{2n}^n$
$\textbf{非法序列个数}$=2n个位置放n-1个-1和n+1个1=$C_{2n}^{n-1}$
$\textbf{合法的序列个数}={C_{2n}^n}-{C_{2n}^{n-1}}={\frac{1}{n+1}*{C_{2n}^n}}$
这就是我们说的卡特兰数公式了

2.n个元素进栈 m个元素出栈 求出栈序列数

看下图

n个元素进栈 m个元素出栈有多少个出栈数
如果我们并不知道如何推算可以直接自己写一个递归函数来算

typedef long long ll;
ll fs[2010][2010];//fs存f(n,m)的答案
ll f(int n,int m){//求n个元素进栈 m个元素出栈有多少种情况的函数
//n<m 不符合定义
    if (n<m) return 0;
//m=0无序列=0
    if (m==0) {
        fs[n][m]=1;
        return 1;
    }
    if (!fs[n][m]) {//记忆化搜索降低复杂度
        fs[n][m]=f(n-1,m)+f(n,m-1);
//对于最后一个入栈的元素 我们将其分解成出栈与不出栈两种情况
        return fs[n][m];
    }
    return fs[n][m];
}

验算可以用n=m的情况输入 看看结果是不是和对应的卡兰特数相同
如果看懂上面的推导
就会发现这其实就是n进n出的另外一个形式
$$\textbf{合法的序列个数=总序列个数-非法序列个数}$$
$\textbf{总序列个数}$=n+m个位置放n个1和m个-1=$C_{n+m}^n$
$\textbf{非法序列个数}$=2n个位置放m-1个-1和m+1个1=$C_{n+m}^{m-1}$
$\textbf{合法的序列个数}={C_{n+m}^n}-{C_{n+m}^{m-1}}$

//补一个小范围求组合数的代码
const int N = 2010,mod=1e9+7;
int c[N][N];
void init(){
    for (int i=0;i<=2000;i++){
        c[i][0]=1;
        for (int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
}