login
Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n and having abscissa of first return equal to 2k (2<=k<=n). A hill in a Dyck path is a peak at level 1.
1

%I #17 Apr 07 2019 01:58:41

%S 1,0,2,1,0,5,2,2,0,14,6,4,5,0,42,18,12,10,14,0,132,57,36,30,28,42,0,

%T 429,186,114,90,84,84,132,0,1430,622,372,285,252,252,264,429,0,4862,

%U 2120,1244,930,798,756,792,858,1430,0,16796,7338,4240,3110,2604,2394,2376,2574,2860,4862,0,58786

%N Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n and having abscissa of first return equal to 2k (2<=k<=n). A hill in a Dyck path is a peak at level 1.

%C Row sums are the Fine numbers (A000957). Column 2 yield the Fine numbers (A000957).

%H G. C. Greubel, <a href="/A114596/b114596.txt">Rows n = 2..100 of triangle, flattened</a>

%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 T(n,n) = Catalan(n-1) (A000108).

%F Sum_{k=2..n} k*T(n,k) = 2*A014301(n).

%F T(n, k) = Catalan(k-1)*f(n-k), for 2<=k<=n, where Catalan(n) are the Catalan numbers (A000108) and f(n) = 3*Sum_{j=0..floor(n/2)} ( binomial(2n-2j, n) ) - binomial(2n+2, n+1) (the Fine numbers, A000957).

%F G.f.: (2*(1+x-t*x) +sqrt(1-4*x) -sqrt(1-4*t*x))/(1 +2*x +sqrt(1-4*x)) -1.

%e T(5,3)=2 because we have UUUDDD|UUDD and UUDUDD|UUDD, where U=(1,1), D=(1,-1) (first return is shown by a vertical bar).

%e Triangle begins:

%e 1;

%e 0, 2;

%e 1, 0, 5;

%e 2, 2, 0, 14;

%e 6, 4, 5, 0, 42;

%e 18, 12, 10, 14, 0, 132;

%p c:=n->binomial(2*n,n)/(n+1): f:=n->3*sum(binomial(2*n-2*j,n),j=0..floor(n/2))-binomial(2*n+2,n+1): for n from 2 to 12 do seq(c(k-1)*f(n-k),k=2..n) od; # yields sequence in triangular form

%t f[n_]:= 3*Sum[Binomial[2*n-2*j, n], {j,0,Floor[n/2]}] - Binomial[2*n+2, n +1]; Table[CatalanNumber[k-1]*f[n-k], {n,2,12}, {k,2,n}] (* _G. C. Greubel_, Apr 06 2019 *)

%o (PARI) {f(n) = 3*sum(j=0, floor(n/2), binomial(2*n-2*j, n)) - binomial(2*n+2, n+1)};

%o for(n=2,12, for(k=2,n, print1((binomial(2*(k-1),k)/(k-1))*f(n-k), ", "))) \\ _G. C. Greubel_, Apr 06 2019

%o (Sage)

%o @CachedFunction

%o def f(n):

%o return 3*sum(binomial(2*n-2*j, n) for j in (0..floor(n/2))) - binomial(2*n+2, n+1)

%o def T(n,k): return catalan_number(k-1)*f(n-k)

%o [[T(n,k) for k in (2..n)] for n in (2..12)] # _G. C. Greubel_, Apr 06 2019

%Y Cf. A000957, A000108, A014301.

%K nonn,tabl

%O 2,3

%A _Emeric Deutsch_, Dec 12 2005

%E Keyword tabf changed to tabl by _Michel Marcus_, Apr 09 2013