■いろいろの漸化式と母関数(その34)

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

  c(n+1)=c(0)c(n)+c(1)c(n−1)+・・・+c(n)c(0)

はよく知られている.ただし,c(0)=1とする.

  c(0)c(0)=c(1)=1

  c(0)c(1)+c(1)c(0)=c(2)=2

  c(0)c(2)+c(1)c(1)+c(2)c(0)=c(3)=5

 これはカタラン数の漸化式であって,カタラン数c(n)はnの増加に応じて急激に増加する.

  c(0)=1,c(1)=1,c(2)=2,c(3)=5,

  c(4)=14,c(5)=42,c(6)=132,

  c(7)=429,c(8)=1430,c(9)=4862,・・・

===================================