|
|
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.
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|