首先知道结论：折现图上最低点的纵坐标为 \(k-m\)。
简单证明：考虑贪心这匹配过程（左括号 +1，右括号 -1），每次如果遇到向下的小于 0 的段，我们把其抹平，然后让后面所有点都 + 上某个值，最后一直这样操作，答案就是在 y 正轴上面的右括号/-1/下降个数。
感性理解就是对于那个最低的在 y 负半轴的位置，显然前面的所有的移动都不会超过这一次的移动，然后这一次移动过后，根据最低点的性质，后面也必定不会 < 0，得证。
问题变成：
从 \((0,0)\) 到 \((n+m,n-m)\) 的折线图经过但不穿过 \(y=k-m\) 的方案数。
首先把平面向左旋转 45 度，让问题变成非降序列计数。终点变成：\((2m,2n)\)。
左上折线变成向上（左括号），左下变成向右。考虑图像的放缩，除以 \(\sqrt 2\) 之后。一次移动的长度就是 \(1\) 了。
然后经过的直线也变成了 \(y=x+(k-m)\)。
Conclusion
-
贪心模拟匹配过程。
-
将过程刻画到折线图上。
-
挖掘出简单性质。
-
转换成格子的非降序列计数，卡特兰计算。