卡塔兰数
$\quad\\$
Catalan Numbers
$\quad\\$
定义卡塔兰数$\text{Cat}_n$如下
$$\text{Cat}_n=\frac{1}{n+1}\left(\begin{array}&2n\\n\end{array}\right),n\in \mathbb{N}$$
由Wallis公式$\frac{(n!)^22^{2n}}{(2n)!}\sim\sqrt{\pi n}$可直接得出卡塔兰数具有如下渐近性质
$$\text{Cat}_n\sim \frac{2^{2n}}{n\sqrt{\pi n}},\text{for}\; n\to\infty$$
$\quad\\$
Dyck Sequences
$\quad\\$
任意给定一个仅由$n$个$0$和$n$个$1$构成的$2n$元二进制序列，如果$\forall 0<i\leq 2n$，均有此序列的前$i$项中$0$的个数大于等于$1$的个数，则称此序列为Dyck-2n序列，记Dyck-2n序列的个数为$N($Dyck-2n$)$，则有
$$N(\textbf{Dyck-2n})=\mathbf{Cat_n}$$
$\nabla$证
$$ 任取一个仅由0和1构成的2n元序列x=(x_1,x_2,\cdots,x_{2n})\\\\ \quad\\\\ 记满足1的个数大于0的个数的最小主子序列长度为i\\\\ \quad\\\\ 如果不存在这样的主子序列，则令i=2n\\\\ \quad\\\\ 记x^{\star}=(x_1,x_2,\cdots,x_i,1-x_{i+1},1-x_{i+2},\cdots,1-x_{2n})\\\\ \quad\\\\ 因为x^{\star\star}=x，故x^{\star}与x建立了一个双射\\\\ \quad\\\\ 如果x是具有占有列(n,n)的非\text{Dyck-2n}序列\\\\ \quad\\\\ 则x^{\star}具有占有列(n-1,n+1)\\\\ \quad\\\\ 反之，如果序列y具有占有列(n-1,n+1)\\\\ \quad\\\\ 则y^{\star}具有占有列(n,n)且一定为非\text{Dyck-2n}序列\\\\ \quad\\\\ 于是x与y之间建立了一个双射，即二者数目相同\\\\ \quad\\\\ 于是\\\\ \quad\\\\ \begin{aligned}N(\text{Dyck-2n})&=占有列为(n,n)的序列数-占有列为(n-1,n+1)的序列数\\\\ &=\left(\begin{array}&2n\\\\n\end{array}\right)-\left(\begin{array}&2n\\\\n-1\end{array}\right)\\\\ &=\frac{2n!}{n!n!}-\frac{2n!}{(n-1)!(n+1)!}\\\\ &=\frac{1}{n+1}\left(\begin{array}&2n\\\\n\end{array}\right)\\\\ &=\text{Cat}_n\end{aligned} $$
$\quad\\$
Raney Lemma
$\quad\\$
为了接下来卡塔兰数的推广，先介绍Raney引理，令$\mathfrak{x}=(x_1,x_2,\cdots,x_n)$为任一整数序列，其和$\sum\limits_{i=1}^nx_i=1$，记其部分和为$S_k=\sum\limits_{i=1}^kx_i$，其循环移位序列为$\mathfrak{x_i}=(x_{i+1},x_{i+2},\cdots,x_n,x_1,\cdots,x_i),0\leq i\leq n-1\;$则该引理可表述如下
$$\small\textbf{在}\mathfrak{x}\textbf{的所有循环移位序列中，仅有一个序列满足其所有部分和均大于零}$$
此引理可利用几何方法证明，先将$\mathfrak{x}=(x_1,x_2,\cdots,x_n)$延拓成无穷周期序列
$\mathfrak{x}_{\infty}=(x_1,x_2,\cdots,x_n,x_1,x_2,\cdots,x_n,\cdots)$ ，将 $\mathfrak{x}_{\infty}$ 的部分和序列$S_k$对$k$作折线图$(k\in \mathbb{N})$，以$\mathfrak{x}=(3,-5,2,-2,3,0)$为例可得如下图形
整个图形处于斜率为$\frac{1}{n}$的与之相切的两条直线之间，且对每条直线，折线图的每个周期$($连续的$n$个点$)$中仅有一点在其上，这是因为折线图每过一个周期往上平移$1(S_n=1)$，两个相邻周期的下直线上的点(绿圈)的线段间不可能再有其他整点，上直线也是如此。现在考虑折线图在一个周期之内的性质，任意连续的$n$个点都对应着一个循环移位序列，此序列的部分和$S_i$就是这$n$个点中第${i+1}$个点的高度减去第$1$个点的高度，因为在下直线上的点总是一个周期中的最低点之一，且其为从自身开始的连续$n$个点中的唯一最低点，故只有这个周期对应的循环移位序列的所有部分和均大于零，此即Raney引理
$\quad\\$
Fuss-Catalan Numbers
$\quad\\$
考察由$1$与$1-m$构成的和为$1$且部分和均大于零的序列$\mathfrak{x}=(x_0,x_1,\cdots,x_{mn})$，可称其为m-Raney序列，设$1$有$k$个，$1-m$有$mn+1-k$个，则$k+mn+1-k-m^2n-m+mk=1$，解得$k=mn+1-n$，
记m-Raney序列共有$\textbf{Cat}_n^m$个，称为富斯-卡塔兰数，于是由Raney引理可知
$$\text{Cat}_n^m=\frac{1}{mn+1}\left(\begin{array}&mn+1\\n\end{array}\right)$$
由于m-Raney序列$\mathfrak{x}$的第一项$x_0$总是$1$，故其可与将首项$x_0$删去的由$mn-n$个$1$与$n$个$1-m$构成的部分和均大于等于零的序列$\mathfrak{x}’=(x_1,\cdots,x_{mn})$建立一一对应，又$\mathfrak{x}’$可与由$(m-1)n$个元素$a$与$n$个元素$b$构成的满足任意主子序列中$a$的个数不小于$m-1$倍$b$的个数的序列$\mathfrak{x}’’$建立一一对应，故$\mathfrak{x}$的个数与$\mathfrak{x}’’$的个数相等，于是可将富斯-卡塔兰数作如下的几何表示
容易看出，在只能向上与向右移动的情况下，富斯-卡塔兰数$\text{Cat}_n^m$即是从左下角的绿色格子移动到右上角绿色格子的路径数[反过来走，出发格视为
$\{(2-m)a,0b\}$]。同时又可以得到由$(m-1)(n+1)$个元素$a$与$n+1$个元素$b$构成的满足任意主子序列中$a$的个数不大于$m-1$倍$b$的个数的序列$\mathfrak{x}’’’$的个数也为$\text{Cat}_n^m$
$\quad\\$
参考与引用来源
$\quad\\$
Discrete Calculus
具体数学$\small \textbf{Introduced by}$ 破壁人5th