A114276 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having length of second ascent equal to k (0<=k<=n-1).

1, 1, 1, 1, 3, 1, 1, 8, 4, 1, 1, 22, 13, 5, 1, 1, 64, 41, 19, 6, 1, 1, 196, 131, 67, 26, 7, 1, 1, 625, 428, 232, 101, 34, 8, 1, 1, 2055, 1429, 804, 376, 144, 43, 9, 1, 1, 6917, 4861, 2806, 1377, 573, 197, 53, 10, 1, 1, 23713, 16795, 9878, 5017, 2211, 834, 261, 64, 11, 1, 1

Offset

1,5

Comments

Column 1 yields A014138, column 2 yields A001453, column 3 yields A114277. Row sums are the Catalan numbers (A000108).

Links

Table of n, a(n) for n=1..67.

Formula

T(n, k)=(k+1)*sum(binomial(2*n-k+1-2*j, n-j+1)/(2*n-k-2*j+1), j=1..n-k) if 1<=k<=n-1; T(n, 0)=1. G.f. = (1-tz)/[(1-z)(1-tzC)]-1 where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.

Example

T(4,2)=4 because we have UD(UU)DDUD, UD(UU)DUDD, UUD(UU)DDD and UUDD(UU)DD (second ascent shown between parentheses).

Maple

T:=proc(n, k) if k=0 then 1 elif k<=n-1 then (k+1)*sum(binomial(2*n-k+1-2*j, n-j+1)/(2*n-k-2*j+1), j=1..n-k) else 0 fi end: for n from 1 to 12 do seq(T(n, k), k=0..n-1) od; # yields sequence in triangular form

Crossrefs

Cf. A000108, A014138, A001453, A114277.

Sequence in context: A351889 A203717 A143953 * A152879 A098747 A122897

Adjacent sequences: A114273 A114274 A114275 * A114277 A114278 A114279

Keyword

nonn,tabl

Author

Emeric Deutsch, Nov 20 2005

Status

approved