两年多之前， @魏俊年 老师在知乎提了个关于Catalan数的问题，我当时写了个回答：在2n个顺序摆放的盒子中填充n个白球和n个黑球，要求任取前m个盒子，其中黑球数目不少于白球？后来想想看，这个回答其实仅仅介绍了Catalan数的通项公式是怎么推导的，却完全没有把来龙去脉介绍清楚，尤其是没有介绍其中引出Catalan数的几个组合模型的等价性一直想抽空写篇文章详细介绍一下，近日得以有空我以尽量初等的语言详细介绍一下Catalan数，以做科普之用，尽量连没有数学竞赛背景的普通中学生都能照顾到引我们知道如果在一条直线上，排列有 n 个元素，其中 n_{1} 个元素彼此相同，另外 n_{2} 个元素彼此相同，…， n_{r} 个元素也彼此相同，并且满足 n=n_{1}+n_{2}+\cdots+n_{r} 则它们共有 \frac{n!}{n_{1}!n_{2}!\cdots n_{r}!} 种排列方式而最简单的情形，就是其中 m 个元素彼此相同，另外 n-m 个元素彼此相同的情况（或者更直观地，想象成 m 个黑球与 n-m 个白球）此时它们在直线上有 \frac{n!}{m!\left( n-m \right)!} 种排列方式而在直线上将这 n 个元素进行排列的方式，又等价于在 n 个位置中取 m 个位置放入其中一种元素，所以才有 {n \choose m}=\frac{n!}{m!\left( n-m \right)!} 黑白球考虑袋子中有 n 个白球与 n 个黑球，将它们从袋子之中逐一取出，直至取完. 在取球过程中，至少有一次取出的白球多于取出的黑球的取法有多少种？解：把球逐一取出，当然是等价于为它们做排列的将 n 个白球与 n 个黑球逐一取出的所有取法，和 n 个白球与 n 个黑球在直线上的排列方式一一对应，当然有 {2n \choose n} 种取法注： {2n \choose n} 有个特别的名称，叫做Central Binomial Coefficient（中心二项式系数）现在考虑集合X=\left\{ 在取球过程中，至少有一次取出的白球多于取出的黑球的取法 \right\} Y=\left\{ 将n+1个白球和n-1个黑球排成一列的方法 \right\} 这样，对于任意取法 x\in X ，根据定义，它必然有某一时刻，首次出现取出的白球多于黑球，此时未取出的球中，黑球数比白球数多1. 将未取出的球，白球与黑球颜色互换，此时仍然总共有 2n 个球，但白球总数变成了 n+1 ，黑球总数变成了 n-1 ，于是就将取法 x 映射成了某个 y\in Y 现在我们证明，这个映射 f:X\rightarrow Y 是一一映射首先，如果有一个不同于 x 的取法 x' ，那么要么在 x' 中第一次出现白球数多于黑球数的时刻不同于取法 x ，要么 x' 与 x 在同一时刻第一次出现白球数多于黑球数，但以后的取法不同（都相同就是完全同样的取法了），不论哪种情况， f\left( x' \right) 均与 y=f\left( x \right) 不同，这就证明了映射 f 是单射其次，对于任意 y\in Y ，按照 y 的排列顺序数过去，在白球个数第一次超过黑球数后，立即将（按此顺序）之后的白球与黑球颜色互换，这就产生了一种取球方法 x\in X ，显然 f\left( x \right)=y ，这就证明了映射 f 是满射这就证明了映射 f:X\rightarrow Y 是一一映射所以自然有 \left
X \right|=\left
Y \right|={2n \choose n+1} 而 @魏俊年 发的那个问题，显然等价于在取球过程中，取出的白球个数永远不超过取出的黑球的取法那么答案自然是{2n \choose n}-{2n \choose n+1}=\frac{1}{n+1}{2n \choose n} 最短路线m,n\in\mathbb{N}^{*} 从原点 \left( 0,0 \right) 沿着坐标网（直线 y=k 和 x=h ， k,h\in\mathbb{N}^{*} ）走到整点 \left( m,n \right) 的最短路线，简称路线从原点 \left( 0,0 \right) 到整点 \left( m,n \right) 的最短路线共有 {m+n \choose m}={m+n \choose n} 条结论是很显然的向右走一个单位相当于一个黑球，向上走一个单位相当于一个白球原问题就变成了 m 个黑球和 n 个白球的排列问题，结论显然由此，如果从原点 \left( 0,0 \right) 出发，沿着坐标网（直线 y=k 和 x=h ， k,h\in\mathbb{N}^{*} ）走到整点 \left( n,n \right) 的最短路线，显然有 {2n \choose n} 条我们令标记 E 表示向东前进一个单位， N 表示向北前进一个单位，显然最后 E 的个数与 N 的个数相等，均为 n 定义：从原点 \left( 0,0 \right) 出发，沿着坐标网（直线 y=k 和 x=h ， k,h\in\mathbb{N}^{*} ）走到整点 \left( n,n \right) 的最短路线中，我们把不在直线 y=x 的上方出现的路线称为Whitworth路线，简称W线我们考虑有多少条W线我们还是令标记 E 表示向东前进一个单位， N 表示向北前进一个单位，显然最后 E 的个数与 N 的个数相等（均为 n ），并且在这过程中的任意时刻， N 的个数不能多于 E 的个数，不然就会跑直线 y=x 的上方了好了，这就显然等价于：袋子中有 n 个白球与 n 个黑球，将它们从袋子之中逐一取出，直至取完，求取球过程中，取出的白球个数永远不超过取出的黑球的取法二者显然是同构的实际上，如果把每一种取球的方法表示成一个序列：a_{1},a_{2},a_{3},\cdots,a_{2n-1},a_{2n} 其中有 n 项是 -1 （白球）， n 项是 +1 （黑球），并且满足a_{1}+a_{2}+\cdots+a_{k-1}+a_{k}\geq0 （其中 k=1,2,\cdots,2n-1,2n ）把 +1 换作路线 E ，把 -1 换作路线 N ，就很直观了添加括号考虑一个代数系统 X ，其中的乘法 * 不满足结合律如果 x_{1},x_{2},\cdots,x_{n}\in X ，并且这 n 个元素不交换顺序，只通过添加括号改变运算顺序，所得出的一切可能的乘积彼此不同，其个数记为 h\left( n \right) ，求 h\left( n \right) 的递推关系不妨设 h\left( 1 \right)=1 ， h\left( 2 \right)=1 显然我们有 h\left( 3 \right)=2 ，因为只有 \left( x_{1}*x_{2} \right)*x_{3} 和
x_{1}*\left(x_{2}*x_{3}\right) 这两种情况考虑一般的 h\left( n \right) （ n\in\mathbb{N}^{*} ）， x_{1}*x_{2}*\cdots*x_{n} 最外层的两对括号形如\left( x_{1}*\cdots*x_{r} \right)*\left( x_{r+1}*\cdots*x_{n} \right) （ 1\leq r\leq n-1 ， n,r\in\mathbb{N}^{*} ）（实际上这是次外层括号，最外层 \left( x_{1}*x_{2}*\cdots*x_{n} \right) 一般省略）其中 r=1 时，通常简记x_{1}*\left( x_{2}*\cdots*x_{n} \right) =\left( x_{1} \right)*\left( x_{2}*\cdots*x_{n} \right) 而 r=n-1 时，简记\left( x_{1}*\cdots*x_{n-1} \right)*x_{n} =\left( x_{1}*\cdots*x_{n-1} \right)*\left( x_{n} \right) 除了这两种情况，其他情况下不省略括号比如 \left( x_{1}*x_{2} \right)*x_{3}=x_{1}*x_{2}*x_{3} ，但我们不省略这个括号这意味着任何一个最内层的括号内只能有两个元素相乘所以，注意到对于\left( x_{1}*\cdots*x_{r} \right)*\left( x_{r+1}*\cdots*x_{n} \right) （ 1\leq r\leq n-1 ， n,r\in\mathbb{N}^{*} ）显然前一个括号内有 h\left( r \right) 种加括号的办法，后一个括号内有 h\left( n-r \right) 种加括号的方法对于每个指定的 r ，当然是 h\left( r \right)h\left( n-r \right) 种加括号的办法当 r 遍历 1,2,\cdots,n-1 时，就形成了递推关系：h\left( n \right) =h\left( 1 \right)h\left( n-1 \right)+h\left( 2 \right)h\left( n-2 \right) +\cdots +h\left( n-2 \right)h\left( 2 \right)+h\left( n-1 \right)h\left( 1 \right) （ n\in\mathbb{N}^{*} ）到后面我们可以知道h\left( n \right)=\frac{1}{n}{2n-2 \choose n-1} 如果令 h\left( n+1 \right)=C\left( n \right) ，则有C\left( n \right) =C\left( 0 \right)C\left( n-1 \right)+C\left( 1 \right)C\left( n-2 \right) +\cdots +C\left( n-2 \right)C\left( 1 \right)+C\left( n-1 \right)C\left( 0 \right) （ n\in\mathbb{N} ）完全二叉树我们考虑有 n 个叶子的完全二叉树的个数 h\left( n \right) 实际上，它完全和上一个代数系统添加括号的问题同构将该完全二叉树的 n 个叶子按顺序分别用 n 个标记x_{1},x_{2},\cdots,x_{n-1},x_{n} 设 v 是二叉树的一个內结点，若 v 的两个子女分别为 c_{1},c_{2} ，则将 v 改写为 \left( c_{1}*c_{2} \right) 这样由根开始，反复改写下去，直到全部改写为 n 个叶子标记的加括号乘法形式显然这就是一种对乘法 x_{1}*x_{2}*\cdots*x_{n} 添加括号的方法（可以省略最外层括号）它们之间显然构成一一对应同构现在，我们要定义一个映射 f ，将所有的W线映射为对乘法 x_{1}*x_{2}*\cdots*x_{n}*x_{n+1} 添加（总共 n-1 个）括号的方法任何一个W线的第一步骤当然是 E （否则就跑直线 y=x 的上方去了）把这第一个 E 删掉，然后把这个W线的每个 N 顺次改成 x_{1}*,x_{2}*,\cdots,x_{n}* ，再在最后添加 x_{n+1} 然后，把每个 E 换成半括号 ( 例如，最短路线 ENEENN 显然是W线，它按照这个步骤，被改造成了如下形式：x_{1}*((x_{2}*x_{3}*x_{4} 然后我们再补齐右半括号，原则是一个（层）括号内有且只有两个元素，被括号括起来的两个相乘的元素整体当成一个元素将所有括号都补全，比如这样： x_{1}*((x_{2}*x_{3})*x_{4}) 对于 x_{1}*x_{2}*\cdots*x_{n}*x_{n+1} ，显然有 n-1 对括号这得出的结果 y 就是元素 x （某条W线）在映射 f 下的像不同的 x 至少存在一个 E 的位置不同，所以具有不同的像，映射 f 是单射而任何一个 y 也可以变成一个W线，方法是：删去 x_{n+1} 和所有半括号 ) ，将 x_{1}*,x_{2}*,\cdots,x_{n}* 全部变成 N ，半括号 ( 全部变成 E ，再在最前面添加一个 E 这说明映射 f 是满射这样映射 f 就构成了一一映射所以 h\left( n+1 \right)=C\left( n \right)=\frac{1}{n+1}{2n \choose n} 实际上数列 \left\{ C\left( n \right) \right\} 的通项公式是直接可求的数列 C\left( 0 \right)=1 ， C\left( 1 \right)=1 满足递推关系： C\left( n \right) =C\left( 0 \right)C\left( n-1 \right)+C\left( 1 \right)C\left( n-2 \right) +\cdots +C\left( n-2 \right)C\left( 1 \right)+C\left( n-1 \right)C\left( 0 \right) 则其通项公式为C\left( n \right)=\frac{1}{n+1}{2n \choose n} （ n\in\mathbb{N} ）关于如何求这个通项公式，有不少种方法，我介绍一下（一）数学归纳法这应该是唯一一种不借助组合数学模型的纯粹初等证法，这种方法虽然只用到初等数学，但技巧性偏高相当于证明恒等式：\sum_{k=1}^{n-1}{\frac{1}{k(n-k)} {2k-2 \choose k-1}{2n-2k-2 \choose n-k-1}} =\frac{1}{n}{2n-2 \choose n-1} （ n\in\mathbb{N}^{*} ， n\geq2 ）注意\frac{n}{k(n-k)}=\frac{1}{k}+\frac{1}{n-k} 由对称性，显然\sum_{k=1}^{n-1}{\frac{1}{k} {2k-2 \choose k-1}{2n-2k-2 \choose n-k-1}} =\sum_{k=1}^{n-1}{\frac{1}{n-k} {2k-2 \choose k-1}{2n-2k-2 \choose n-k-1}} \sum_{k=1}^{n-1}{\frac{n}{k(n-k)} {2k-2 \choose k-1}{2n-2k-2 \choose n-k-1}} =2\sum_{k=1}^{n-1}{\frac{1}{k} {2k-2 \choose k-1}{2n-2k-2 \choose n-k-1}} 于是它等价于证明恒等式\sum_{k=1}^{n-1}{\frac{1}{k} {2k-2 \choose k-1}{2n-2k-2 \choose n-k-1}} =\frac{1}{2}{2n-2 \choose n-1} （ n\in\mathbb{N}^{*} ， n\geq2 ）n=2 时显然它是成立的假设 n=m 时它也成立，即\sum_{k=1}^{m-1}{\frac{1}{k} {2k-2 \choose k-1}{2m-2k-2 \choose m-k-1}} =\frac{1}{2}{2m-2 \choose m-1} \sum_{k=1}^{m}{\frac{1}{k} {2k-2 \choose k-1}{2m-2k \choose m-k}} =\sum_{k=1}^{m-1}{\frac{1}{k} {2k-2 \choose k-1}{2m-2k \choose m-k}} +{\frac{1}{m} {2m-2 \choose m-1}} 注意：\begin{alignat}{0} {2m-2k \choose m-k}=\frac{(2m-2k)!}{((m-k)!)^{2}}\\ =\frac{(2m-2k)(2m-2k-1)}{(m-k)^{2}} \frac{(2m-2k-2)!}{((m-k-1)!)^{2}}\\ =\left( 4-\frac{2}{m-k} \right){2m-2k-2 \choose m-k-1} \end{alignat} 这样可得\begin{alignat}{0} \sum_{k=1}^{m}{\frac{1}{k} {2k-2 \choose k-1}{2m-2k \choose m-k}}\\ =\sum_{k=1}^{m-1}{\frac{1}{k}\left( 4-\frac{2}{m-k} \right) {2k-2 \choose k-1}{2m-2k-2 \choose m-k-1}} +{\frac{1}{m} {2m-2 \choose m-1}}\\ =4\sum_{k=1}^{m-1}{\frac{1}{k} {2k-2 \choose k-1}{2m-2k-2 \choose m-k-1}}\\ -\frac{2}{m}\sum_{k=1}^{m-1}{\frac{m}{k(m-k)} {2k-2 \choose k-1}{2m-2k-2 \choose m-k-1}} +{\frac{1}{m}{2m-2 \choose m-1}}\\ =4\left( 1-\frac{1}{m} \right)\sum_{k=1}^{m-1}{\frac{1}{k} {2k-2 \choose k-1}{2m-2k-2 \choose m-k-1}} +{\frac{1}{m}{2m-2 \choose m-1}}\\ =2\left( 1-\frac{1}{m} \right){2m-2 \choose m-1} +{\frac{1}{m}{2m-2 \choose m-1}}\\ =\frac{2m-1}{m}\frac{(2m-2)!}{((m-1)!)^{2}}\\ =\frac{1}{2}\frac{(2m)!}{(m!)^{2}}\\ =\frac{1}{2}{2m \choose m}\end{alignat} 便由数学归纳法证明了\sum_{k=1}^{n-1}{\frac{1}{k} {2k-2 \choose k-1}{2n-2k-2 \choose n-k-1}} =\frac{1}{2}{2n-2 \choose n-1} 也即\sum_{k=1}^{n-1}{\frac{1}{k(n-k)} {2k-2 \choose k-1}{2n-2k-2 \choose n-k-1}} =\frac{1}{n}{2n-2 \choose n-1} （ n\in\mathbb{N}^{*} ， n\geq2 ）（二）母函数法这是比较常规的做法令 A\left( x \right)=\sum_{n=0}^{\infty}{C\left( n \right)x^{n}} 则 A\left( x \right) =C\left( 0 \right)+C\left( 1 \right)x+C\left( 2 \right)x^{2}+\cdots +C\left( n \right)x^{n}+\cdots 显然由递推关系\begin{alignat}{0} A\left( x \right) =1+x+\left[ C\left( 0 \right)C\left( 1 \right) +C\left( 1 \right)C\left( 0 \right) \right]x^{2}+\\ \left[ C\left( 0 \right)C\left( 2 \right)+C^{2}\left( 1 \right) +C\left( 2 \right)C\left( 0 \right) \right]x^{3} +\cdots\\ +\left[ C\left( 0 \right)C\left( n-1 \right) +C\left( 1 \right)C\left( n-2 \right) +\cdots +C\left( n-2 \right)C\left( 1 \right) +C\left( n-1 \right)C\left( 0 \right) \right]x^{n} +\cdots\\ \end{alignat} 根据形式幂级数Cauchy卷积的规则，有\begin{alignat}{0} A^{2}\left( x \right) =1+\left[ C\left( 0 \right)C\left( 1 \right) +C\left( 1 \right)C\left( 0 \right) \right]x +\cdots\\ +\left[ C\left( 0 \right)C\left( n-1 \right) +C\left( 1 \right)C\left( n-2 \right) +\cdots +C\left( n-2 \right)C\left( 1 \right) +C\left( n-1 \right)C\left( 0 \right) \right]x^{n-1}\\ +\left[ C\left( 0 \right)C\left( n \right) +C\left( 1 \right)C\left( n-1 \right) +\cdots +C\left( n-1 \right)C\left( 1 \right) +C\left( n \right)C\left( 0 \right) \right]x^{n}\\ +\cdots \end{alignat} 显然A\left( x \right)=1+xA^{2}\left( x \right) 所以A\left( x \right)=\frac{1-\sqrt{1-4x}}{2x} （另一解舍去，因为在 x=0 处将导致无穷大）由牛顿二项式定理 \left( 1+x \right)^{\alpha} =1+\alpha x+\frac{\alpha\left( \alpha-1 \right)}{2!}x^{2}+\cdots +\frac{\alpha\left( \alpha-1 \right)\cdots \left( \alpha-n+1 \right)}{n!}x^{n}+\cdots 即 \left( 1+x \right)^{\alpha} =\sum_{n=0}^{\infty}{{\alpha \choose n}x^{n}} （ \alpha\in\mathbb{R} ）代入 \alpha=-\frac{1}{2} 得 \frac{1}{\sqrt{1+x}} =1-\frac{x}{2}+\frac{1\cdot3}{2\cdot4}x^{2} -\frac{1\cdot3\cdot5}{2\cdot4\cdot6}x^{3}+\cdots +\left( -1 \right)^{n} \frac{\left( 2n-1 \right)!!} {\left( 2n \right)!!}x^{n} +\cdots 再用 -4x 取代 x即得 \frac{1}{\sqrt{1-4x}} =1+2x+6x^{2}+20x^{3}+\cdots +\frac{\left( 2n \right)!}{\left( n! \right)^{2}}x^{n} +\cdots 将之逐项积分注意到\int_{0}^{x}\frac{\mathrm{d}t}{\sqrt{1-4t}}=\frac{1-\sqrt{1-4x}}{2} 由幂级数的逐项可积性\begin{alignat}{0}\frac{1-\sqrt{1-4x}}{2}\\ =x+x^{2}+2x^{3}+5x^{4}+\cdots +\frac{\left( 2n-2 \right)!}{n\left( \left( n-1 \right)! \right)^{2}}x^{n}
+\frac{\left( 2n \right)!} {\left( n+1 \right)\left( n!\right)^{2}}x^{n+1}+\cdots\\ =\sum_{n=1}^{\infty}{\frac{\left( 2n-2 \right)!} {n\left( \left( n-1 \right)! \right)^{2}}x^{n}}\end{alignat} \begin{alignat}{0} A\left( x \right)=\frac{1-\sqrt{1-4x}}{2x}\\ =1+x+2x^{2}+5x^{3}+\cdots +\frac{\left( 2n \right)!}{\left( n+1 \right)\left( n! \right)^{2}}x^{n} +\cdots\\ =\sum_{n=0}^{\infty}{\frac{\left( 2n \right)!}{\left( n+1 \right)\left( n! \right)^{2}}x^{n}} =\sum_{n=0}^{\infty}{C\left( n \right)x^{n}} \end{alignat} 所以C\left( n \right) =\frac{\left( 2n \right)!}{\left( n+1 \right)\left( n! \right)^{2}} =\frac{1}{n+1}{2n \choose n} 或者还可以代入 \alpha=\frac{1}{2} 得到\sqrt{1+x}=1+\frac{x}{2} -\frac{1}{2\cdot4}x^{2}+\frac{1\cdot3}{2\cdot4\cdot6}x^{3} +\cdots +\left( -1 \right)^{n-1} \frac{\left( 2n-3 \right)!!}{\left( 2n \right)!!}x^{n}+\cdots 用 -4x 取代 x ，可得\begin{alignat}{0} \sqrt{1-4x}= 1-2x-2x^{2}-4x^{3}-\cdots-\frac{\left( 2n \right)!} {\left( 2n-1 \right)\left( n! \right)^{2}}x^{n} -\cdots\\ =1-2\sum_{n=1}^{\infty}{\frac{\left( 2n-2 \right)!} {n\left( \left( n-1 \right)! \right)^{2}}x^{n}}\end{alignat}
也即\begin{alignat}{0}\frac{1-\sqrt{1-4x}}{2}\\ =x+x^{2}+2x^{3}+5x^{4}+\cdots +\frac{\left( 2n-2 \right)!} {n\left( \left( n-1 \right)! \right)^{2}}x^{n}
+\frac{\left( 2n \right)!} {\left( n+1 \right)\left( n!\right)^{2}}x^{n+1}+\cdots\\ =\sum_{n=1}^{\infty} {\frac{\left( 2n-2 \right)!}{n\left( \left( n-1 \right)! \right)^{2}}x^{n}} =\sum_{n=1}^{\infty}{C\left( n-1 \right)x^{n}} =\sum_{n=0}^{\infty}{C\left( n \right)x^{n+1}} \end{alignat} 所以C\left( n \right) =\frac{\left( 2n \right)!}{\left( n+1 \right)\left( n! \right)^{2}} =\frac{1}{n+1}{2n \choose n} 参考资料：单墫《数学奥林匹克命题人讲座 集合与对应》，上海科技教育出版社许胤龙、孙淑玲《组合数学引论》，中国科学技术大学出版社Kenneth H.Rosen《离散数学及其应用》，机械工业出版社杨子胥《高等代数习题解》，山东科学技术出版社Richard P. Stanley《Enumerative Combinatorics, Volume 2》，Cambridge University Press