几何法证明卡特兰数_栈混洗

模型：

考虑从坐标原点 (0, 0) 到点 (n, n) 的路径，要求路径只能向右（x 方向）或向上（y 方向）移动，并且路径不能越过直线 y = x（即始终满足 y<= x ）。这样的路径数量就是卡特兰数 Cn 所表示的组合数量。
 

对于栈的操作:

将入栈约等于向右移动一步（x 方向），出栈约等于向上移动一步（y 方向）。因为栈在任何时刻出栈操作次数不能超过入栈操作次数，所以对应的路径不能越过 y = x 这条线。

设 SP(n) 表示对 n 个元素进行合法栈操作（入栈 n 次，出栈 n 次 ，且任何时刻出栈次数不超过入栈次数 ）的序列个数，这就和上述从 (0,0) 到 (n,n) 且不越过 y = x 的路径数建立起一一对应关系。

计算从 (0, 0) 到 (n, n) 的总路径数：
从 (0, 0) 到 (n, n) 总共要走 2n 步，其中 n 步向右，n 步向上，根据组合数公式，总路径数为 

 对于一条越过 y = x 的路径，必然会与直线 y=x + 1 有交点。设第一次与 y=x + 1 相交的点为 P ，将从原点到 P 的路径关于 y=x + 1 对称，再连接对称后的终点与 (n,n) ，可以发现越过 y = x 的路径与从 (0,0) 到 (n - 1,n + 1) 的路径是一一对应的。
从 (0, 0) 到 (n - 1,n + 1) 总共走 2n 步，其中 n - 1 步向右，n + 1 步向上，路径数为

 计算不越过 y = x 的路径数（即卡特兰数 Cn ）：
用从 (0, 0) 到 (n, n) 的总路径数减去越过 y = x 的路径数，即

 由于 SP(n) 所代表的合法栈操作序列个数与从 (0,0) 到 (n,n) 且不越过 y = x 的路径数相等，所以

 即 SP(n) 等于卡特兰数。

 

https://dsa.cs.tsinghua.edu.cn/~deng/ds/dsacpp/

https://zhuanlan.zhihu.com/p/166135630?utm_psn=1891333928486429828