Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!

小思Catalan数

 什么是Catalan数

说到Catalan数,就不得不提及Catalan序列,Catalan序列是一个整数序列,其通项公式是C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \quad n\ge 0我们从中取出的C_n就叫做第n个Catalan数,前几个Catalan数是:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, …咋看之下没什么特别的,但是Catalan数却是许多计数问题的最终形式。

继续阅读