■カタラン数(その7)
(その6)ではカタラン数を拡張した.
Cn=C(n,n)
===================================
[1]0≦p≦qのとき,
C(p,q)=C(p,q−1)+C(p−1,q)
C(0,0)=1
[2]p<0またはp>qのとき,C(p,q)=0
C(0,0)
C(0,1),C(1,1)
C(0,2),C(1,2,),C(2,2)
のように,それぞれの項が上と左の項の和であるような三角形配列を作ると
1
1,1
1,2,2
1,3,5,5
1,4,9,14,14
1,5,14,28,42,42
1,6,20,48,90,132,132
ができる.
一般項は
C(p,q)=(q−p+1)/(q+1)・(p+q,p)
=(p+q,p)−(p+q,p−1)
0≦p<nについて,
ΣC(n−k,n−1−p)C(p,q)=C(n,n)
===================================