|
%I #4 Mar 30 2012 17:36:07
%S 1,1,2,4,1,12,2,37,5,119,12,1,390,36,3,1307,114,9,4460,376,25,1,15452,
%T 1262,78,4,54207,4310,255,14,192170,14934,863,44,1,687386,52397,2967,
%U 145,5,2477810,185780,10338,492,20,8992007,664631,36424,1712,70,1
%N 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.
%C 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).
%F G.f.=1/(1+z^3-tz^3-zC), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.
%e 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.
%e Triangle starts:
%e 1;
%e 1;
%e 2;
%e 4,1;
%e 12,2;
%e 37,5;
%e 119,12,1;
%e 390,36,3;
%e 1307,114,9;
%p 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
%Y Cf. A000108, A114500.
%K nonn,tabf
%O 0,3
%A _Emeric Deutsch_, Dec 04 2005
|
