A114499 Triangle read by rows: number of Dyck paths of semilength n having k 3-bridges of a given shape (0<=k<=floor(n/3)). A 3-bridge is a subpath of the form UUUDDD or UUDUDD starting at level 0.

1, 1, 2, 4, 1, 12, 2, 37, 5, 119, 12, 1, 390, 36, 3, 1307, 114, 9, 4460, 376, 25, 1, 15452, 1262, 78, 4, 54207, 4310, 255, 14, 192170, 14934, 863, 44, 1, 687386, 52397, 2967, 145, 5, 2477810, 185780, 10338, 492, 20, 8992007, 664631, 36424, 1712, 70, 1

Offset

0,3

Comments

Row n has 1+floor(n/3) terms. Row sums are the Catalan numbers (A000108). Column 0 is A114500. Sum(kT(n,k),k=0..floor(n/3))=Catalan(n-2) (n>=3; A000108).

Links

Table of n, a(n) for n=0..50.

Formula

G.f.=1/(1+z^3-tz^3-zC), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.

Example

T(4,1)=2 because we have UD(UUUDDD) and (UUUDDD)UD (or UD(UUDUDD) and (UUDUDD)UD). The 3-bridges are shown between parentheses.
Triangle starts:
1;
1;
2;
4,1;
12,2;
37,5;
119,12,1;
390,36,3;
1307,114,9;

Maple

C:=(1-sqrt(1-4*z))/2/z: G:=1/(1-z*C+z^3-t*z^3): Gser:=simplify(series(G, z=0, 20)): P[0]:=1: for n from 1 to 17 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 17 do seq(coeff(t*P[n], t^j), j=1..1+floor(n/3)) od; # yields sequence in triangular form

Crossrefs

Cf. A000108, A114500.

Sequence in context: A246188 A135333 A124503 * A030730 A117131 A204117

Adjacent sequences: A114496 A114497 A114498 * A114500 A114501 A114502

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 04 2005

Status

approved