卡特兰数

· · 算法·理论

思考一个这样的问题：

有一个 n\times n 大小的矩阵，我们从左下角出发，到达右上角，每次只能往右或者往上走，且不能越过对角线，求方案数。

组合意义证明

我们发现，若不考虑对角线的限制，显然答案为 \binom{2n}{n}。

现在需要考虑跨过对角线的非法方案数，最后答案减去即可。

我们考虑第一次越过对角线时，发现一件事情，若将最后一个路径翻转，必然会走到 (n-1,n+1) 或者 (n+1,n-1) 的位置，但是没有越过对角线的方案是不会这样的，所以我们得到一个结论就是，非法方案数和到达 (n+1,n-1) 或者 (n-1,n+1) 的方案数个数相同，所以可以得到最后答案为 \binom{2n}{n}-\binom{2n}{n+1}。

生成函数证明

定义下降幂为 n^{\underline{m} }=\prod\limits_{i=n-m+1}^{n}{i}

那么 \forall n\in C,m\in N,\binom{n}{m}=\frac{n^{\underline{m}}}{m!}

对于牛顿二项式推广有

\large\forall n\in C,(x+y)^n=\sum\limits_{k=0}^{\infty}\binom{n}{k}x^ky^{n-k}

我们设 H_n 表示的是一个 n\times n 大小的方阵不经过对角线从左下到右上的方案数，我们考虑 H_{n-1} 之前的全部已知，我们计算 H_n 的答案的时候不妨枚举到对角线的哪部分，显然的可以得到一个卷积形式的式子

\large H_n=\sum\limits_{k=0}^{n-1}H_kH_{n-k-1}

考虑用生成函数求该式子。

生成函数即定义一个无穷形式幂函数

\large G(x)=\sum\limits_{k=0}^{\infty}H_kx^k

那么容易有

G(x)=xG^2(x)+1

原因手玩一下就会发现，这里不多讨论。

整理可得

\large G(x)=\frac{1\pm\sqrt{1-4x}}{2x}

我们这里取负号可得

\large 2xG(x)=1-\sum\limits_{k=0}^{\infty}\binom{\frac{1}{2}}{k}(-4)^kx^k \large=-\sum\limits_{k=1}^{\infty}\frac{(\frac{1}{2})^{\underline{k}}}{k!}(-4)^kx^k

考虑整理 \frac{(\frac{1}{2})^{\underline{k}}}{k!}(-4)^k

我们有

\large(\frac{1}{2})^{\underline{k}}=\prod_{i=1}^{k}(\frac{1}{2}-i+1) \large=\prod_{i=1}^{k}(-1)(i-\frac{3}{2}) \large=(-1)^k\prod_{i=1}^{k}(i-\frac{3}{2}) \large=\frac{(-1)^k}{2^k}\prod_{i=1}^{k}(2i-3) \large=\frac{(-1)^{k+1}}{2^k}\prod_{i=1}^{k-1}(2i-1) \large=\frac{(-1)^{k+1}}{2^k}\frac{(2k-3)!}{\prod_{i=1}^{k-2}2i} \large=\frac{(-1)^{k+1}}{2^k}\frac{(2k-3)!}{2^{(k-2)}(k-2)!}

那么乘上一个 (-4)^k 就有

\text{原式}=(-4)\frac{(2k-3)!}{(k-2)!}

放到原式子里面就有

\large 2xG(x)=\sum\limits_{k=1}^{\infty}4\frac{(2k-3)!}{(k-2)!k!}x^k \large G(x)=\sum\limits_{k=0}^{\infty}2\frac{(2k-1)!}{(k-1)!(k+1)!}x^k \large=\sum\limits_{k=0}^{\infty}2\frac{k}{2k(k+1)}\frac{(2k)!}{k!k!}x^k \large=\sum\limits_{k=0}^{\infty}\frac{1}{k+1}\binom{2k}{k}x^k \large=\sum\limits_{k=0}^{\infty}(\binom{2k}{k}-\binom{2k}{k+1})x^k

证毕

卡特兰自卷积

设 G(x) 为卡特兰数的生成函数，求 [x^n]G^m(x)，这里 [x^n]f(x) 指无穷形势幂级数的第 x^n 项的系数是多少。

先给结论：

\large [x^n]G^m(x)=\binom{2n+m-1}{n+m-1}-\binom{2n+m-1}{n+m}

我想到一个绝妙的证明方法，可惜这里地方太小写不下（bushi）

证明暂时还没想好怎么说明比较好，这里先给个提示是往分割转相同物品的方向，和板插法有点像，可以先自己尝试证明，以后有时间再回来更新（。