抛出一个问题：

一个长度是2n的0/1串，包含n个0以及n个1，需要保证对于任何一个k<=2m满足1~k中0的个数要大于等于1的个数。
问方案数：

看起来好像好难...

Catalan数

显然我们知道在总方案数是\(C_{2n}^{n}\)

使用容斥原理

减去那些不合法的
我们需要证明两个引理：

①每一个问题中不合法的序列都一定对应一个有(n+1)个0和(n-1)个1的序列。
②对于一个有(n+1)个0和(n-1)个1的序列一定对应一个问题中的不合法序列。

要想得到证明我们必须证明这两个引理：

①对于一个不合法序列一定可以找到一个k满足

• 第k个数是1
• 1~k-1的01个数相同

那么这个序列就是不合法的。
如果我们将1~k位上的数分别取反，得到的另一个串，这一定是包含(n+1)个0，(n-1)个1的序列，这样就证明了每一个问题中不合法的序列都一定对应一个有(n+1)个0和(n-1)个1的序列。

②用上述方法可以很容易的证得对于一个有(n+1)个0和(n-1)个1的序列一定对应一个问题中的不合法序列。

于是这样我们就可以推出\[Cnt_n=C^n_{2n}-C^{n+1}_{2n}\]

这样我们来简化一下式子：
\[C^n_{2n}-C^{n+1}_{2n}\]
\[=\frac{(2n)!}{(n!)^2}-\frac{(2n)!}{(n+1)!(n-1)!}\]
\[=\frac{ (2n)! [(n+1)!(n-1)!-(n!)^2]}{(n!)^2 (n+1)! (n-1)!}\]
\[=\frac{ (2n)! [ \frac{(n+1)!n!}{n}-(n!)^2 ]}{(n!)^2 (n+1)! (n-1)!}\]
\[=\frac{ (2n)! [ \frac{(n+1)!n!-(n!)^2·n}{n} ]}{(n!)^2 (n+1)! (n-1)!}\]
\[=\frac{ (2n)! [ \frac{n![(n+1)!-n!·n]}{n} ]}{(n!)^2 (n+1)! (n-1)!}\]
\[=\frac{ (2n)! (n-1)!n! }{(n!)^2 (n+1)! (n-1)!}\]
\[=\frac{ (2n)!}{n! (n+1)!}\]
\[=\frac{ (2n)!}{(n!)^2 (n+1)}\]
\[=\frac{C^n_{2n}}{n+1}\]

所以
\[Cnt_n=\frac{C^n_{2n}}{n+1}\]

Catalan数的应用有很多，比如合法的括号序列个数、n个点组成的二叉树个数....

Catalan数

原文：https://www.cnblogs.com/Chandery/p/11720500.html