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,3

Comments

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

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.

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.

Example

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;

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

Prog

(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

Crossrefs

Cf. A000957, A000108, A014301.

Sequence in context: A133727 A103185 A130513 * A083417 A021479 A073583

Adjacent sequences: A114593 A114594 A114595 * A114597 A114598 A114599

Keyword

nonn,tabl

Author

Emeric Deutsch, Dec 12 2005

Extensions

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

Status

approved