学习笔记04-卡特兰数

· · 个人记录

1 前言

卡特兰数是计数问题中的重要数列，在此做个笔记总结一下。

2 定义

2.0 注意事项

  1. 因为实在难找到合适的基本概念，故直接引入通项式。
  2. 在本文中，为了不让卡特兰数符号与组合数冲突，就用 F_n 来表示卡特兰数的第 n 项，组合数还是用 C_n^m 的形式。

2.1 通项式

设卡特兰数的第 n 项为 F_n，则有如下通项公式：

F_n=C_{2n}^n-C_{2n}^{n+1}

这个式子在实际应用中特别广泛，某些计数问题需要用到上述公式来求卡特兰数。

但有没有化简的办法呢？

答案是肯定的：

C_{2n}^n-C_{2n}^{n+1} =\dfrac{(2n)!}{n!n!}-\dfrac{(2n)!}{(n+1)!(n-1)!} =\dfrac{1}{n+1}[\dfrac{(2n)!(n+1)}{n!n!}-\dfrac{(2n)!}{n!(n-1)!}] =\dfrac{1}{n+1}[\dfrac{(2n)!(n+1)}{n!n!}-\dfrac{n\times (2n)!}{n!n!}] =\dfrac{1}{n+1}\dfrac{(2n)!(n+1-n)}{n!n!} =\dfrac{1}{n+1}\dfrac{(2n)!}{n!n!} =\dfrac{1}{n+1}C_{2n}^n =\dfrac{C_{2n}^n}{n+1}