卡特兰数

思考一个这样的问题：

有一个 $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$

那么容易有

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

整理可得

$\large G(x)=\frac{1\pm\sqrt{1-4x}}{2x}$ 我们这里取负号可得

$\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）

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