カタラン数でも積和型の漸化式

<P />　　ｃ（ｎ＋１）＝ｃ（０）ｃ（ｎ）＋ｃ（１）ｃ（ｎ−１）＋・・・＋ｃ（ｎ）ｃ（０）

はよく知られている．

ただし，ｃ（０）とする．

　　ｃ（０）ｃ（０）＝ｃ（１）＝１

　　ｃ（０）ｃ（１）＋ｃ（１）ｃ（０）＝ｃ（２）＝２

　　ｃ（０）ｃ（２）＋ｃ（１）ｃ（１）＋ｃ（２）ｃ（０）＝ｃ（３）＝５

　これはカタラン数の漸化式であって，カタラン数ｃ（ｎ）はｎの増加に応じて急激に増加する．

　　ｃ（０）＝１，ｃ（１）＝１，ｃ（２）＝２，ｃ（３）＝５，

　　ｃ（４）＝１４，ｃ（５）＝４２，ｃ（６）＝１３２，

　　ｃ（７）＝４２９，ｃ（８）＝１４３０，ｃ（９）＝４８６２，・・・

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝