组合数学¶
插板¶
对于不定方程\(x_1+x_2+....+x_n=M\)解的个数用隔板法可解决：
利用统一加解决\(x_i\ge k\)的问题。
利用容斥解决\(x_i\le k\)的问题。
若条件为\(max\enspace x_i=k\)，则可以化为\(x_i\le k\)的个数减去\(x_i\le k-1\)的个数。
卡特兰数¶
对于长度为\(2n\)的合法括号序列为多少？
可以化为在每一个前缀中，左括号数目永远大于右括号数目，最终左括号数目等于又括号数目。
化到二维平面上，即从\((0,0)\)走到\((n,n)\)路径不触碰（注意是不触碰，而不是碰到）\(y=x+1\)：
考虑单步容斥，计算所有不合法路径总数。
考虑不合法的路径从第一次跟这个直线相交到末尾到\((n,n)\)的路线全部翻折。
每个不合法的路径都可对应一个到\((n-1,n+1)\)的路径。
而所有到\((n-1,n+1)\)的路径一定与这个直线相交，都可反过来转化成不合法的路径。
成一一对应的关系，所以不合法的方案总数等于从\((0,0)\)到\((n-1,n+1)\)的方案总数，为\(C(2n,n-1)\)。
所以\(Catalan(n)=C(2n,n)-C(2n,n-1)\)。
P1641:一样的分析方法，答案为\(C(n+m,n)-C(n+m,m-1)\)
折线法小扩展：
¶
