login
Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n and having k valleys strictly above the x-axis (0<=k<=n-2; n>=2). A hill in a Dyck path is a peak at level 1.
1

%I #7 Apr 06 2019 09:29:42

%S 1,1,1,2,3,1,3,8,6,1,5,18,23,10,1,8,38,70,54,15,1,13,76,186,215,110,

%T 21,1,21,147,451,710,560,202,28,1,34,277,1025,2065,2269,1288,343,36,1,

%U 55,512,2220,5480,7854,6321,2688,548,45,1,89,932,4634,13574,24227,25830

%N Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n and having k valleys strictly above the x-axis (0<=k<=n-2; n>=2). A hill in a Dyck path is a peak at level 1.

%C Row sums yield the Fine numbers (A000957). T(n,0)=A000045(n-1) (the Fibonacci numbers). T(n,1)=A006478(n). Sum(k*T(n,k),k=0..n-2)=A119012(n)

%H E. Deutsch and L. Shapiro, <a href="https://doi.org/10.1016/S0012-365X(01)00121-2">A survey of the Fine numbers</a>, Discrete Math., 241 (2001), 241-265.

%F G.f.: G(t,z)=1/[1-zr(t,z)]-1, where r=r(t,z) is the Narayana function, defined by (1+r)(1+tr)z=r, r(t,0)=0. See Maple program for the explicit form of G(t,z).

%e T(5,2)=6 because we have uud|ud|uuddd, uuudd|ud|udd, uud|uudd|udd, uuud|ud|uddd, uuud|udd|udd and uud|uud|uddd (the valleys above the x-axis are marked with |).

%e Triangle starts:

%e 1;

%e 1,1;

%e 2,3,1;

%e 3,8,6,1;

%e 5,18,23,10,1;

%p G:=2*t/(2*t+z*t+z-1+sqrt(z^2*t^2-2*z^2*t-2*z*t+z^2-2*z+1))-1: Gser:=simplify(series(G,z=0,15)): for n from 2 to 12 do P[n]:=sort(coeff(Gser,z^n)) od: for n from 2 to 12 do seq(coeff(P[n],t,j),j=0..n-2) od; # yields sequence in triangular form

%Y Cf. A000957, A000045, A006478, A119012.

%K nonn,tabl

%O 2,4

%A _Emeric Deutsch_, May 08 2006