A114596 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, 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, 429, 186, 114, 90, 84, 84, 132, 0, 1430, 622, 372, 285, 252, 252, 264, 429, 0, 4862, 2120, 1244, 930, 798, 756, 792, 858, 1430, 0, 16796, 7338, 4240, 3110, 2604, 2394, 2376, 2574, 2860, 4862, 0, 58786

Offset: 2

Author

Emeric Deutsch, Dec 12 2005

Keywords

• nonn
• tabl

Comments

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

Examples

			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).
Triangle begins:
   1;
   0,  2;
   1,  0,  5;
   2,  2,  0, 14;
   6,  4,  5,  0, 42;
  18, 12, 10, 14,  0, 132;
		

Links

• G. C. Greubel, Rows n = 2..100 of triangle, flattened
• E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

Crossrefs

Cf. A000957, A000108, A014301.

Programs

Maple

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

Mathematica

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 *)

PARI

{f(n) = 3*sum(j=0, floor(n/2), binomial(2*n-2*j, n)) - binomial(2*n+2, n+1)};
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

Sage

@CachedFunction
def f(n):
  return 3*sum(binomial(2*n-2*j, n) for j in (0..floor(n/2))) - binomial(2*n+2, n+1)
def T(n,k): return catalan_number(k-1)*f(n-k)
[[T(n,k) for k in (2..n)] for n in (2..12)] # G. C. Greubel, Apr 06 2019

Formula

T(n,n) = Catalan(n-1) (A000108).

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

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).

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

Extensions

Keyword tabf changed to tabl by Michel Marcus, Apr 09 2013