A065602 Triangle T(n,k) giving number of hill-free Dyck paths of length 2n and having height of first peak equal to k.

1, 1, 1, 3, 2, 1, 8, 6, 3, 1, 24, 18, 10, 4, 1, 75, 57, 33, 15, 5, 1, 243, 186, 111, 54, 21, 6, 1, 808, 622, 379, 193, 82, 28, 7, 1, 2742, 2120, 1312, 690, 311, 118, 36, 8, 1, 9458, 7338, 4596, 2476, 1164, 474, 163, 45, 9, 1, 33062, 25724, 16266, 8928, 4332, 1856, 692, 218, 55, 10, 1

Offset: 2

Author

N. J. A. Sloane, Dec 02 2001

Keywords

• nonn
• tabl
• easy
• nice

Comments

A Riordan triangle.

Subtriangle of triangle in A167772. - Philippe Deléham, Nov 14 2009

Riordan array (f(x), x*g(x)) where f(x) is the g.f. of A000958 and g(x) is the g.f. of A000108. - Philippe Deléham, Jan 23 2010

Examples

			T(3,2)=1 reflecting the unique Dyck path (UUDUDD) of length 6, with no hills and height of first peak equal to 2.
Triangle begins:
     1;
     1,    1;
     3,    2,    1;
     8,    6,    3,   1;
    24,   18,   10,   4,   1;
    75,   57,   33,  15,   5,   1;
   243,  186,  111,  54,  21,   6,  1;
   808,  622,  379, 193,  82,  28,  7,  1;
  2742, 2120, 1312, 690, 311, 118, 36,  8,  1;
		

Links

• Reinhard Zumkeller, Rows n = 2..125 of triangle, flattened
• Emeric Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

Crossrefs

Row sums give A000957 (the Fine sequence).

First column is A000958.

Cf. A000108, A007318, A167772.

Programs

Haskell

a065602 n k = sum
   [(k-1+2*j) * a007318' (2*n-k-1-2*j) (n-1) `div` (2*n-k-1-2*j) |
    j <- [0 .. div (n-k) 2]]
a065602_row n = map (a065602 n) [2..n]
a065602_tabl = map a065602_row [2..]
-- Reinhard Zumkeller, May 15 2014

Maple

a := proc(n,k) if n=0 and k=0 then 1 elif k<2 or k>n then 0 else sum((k-1+2*j)*binomial(2*n-k-1-2*j,n-1)/(2*n-k-1-2*j),j=0..floor((n-k)/2)) fi end: seq(seq(a(n,k),k=2..n),n=1..14);

Mathematica

nmax = 12; t[n_, k_] := Sum[(k-1+2j)*Binomial[2n-k-1-2j, n-1] / (2n-k-1-2j), {j, 0, (n-k)/2}]; Flatten[ Table[t[n, k], {n, 2, nmax}, {k, 2, n}]] (* Jean-François Alcover, Nov 08 2011, after Maple *)

SageMath

def T(n,k): return sum( (k+2*j-1)*binomial(2*n-2*j-k-1, n-1)/(2*n-2*j-k-1) for j in (0..(n-k)//2) )
flatten([[T(n,k) for k in (2..n)] for n in (2..12)]) # G. C. Greubel, May 26 2022

Formula

T(n, 2) = A000958(n-1).

Sum_{k=2..n} T(n, k) = A000957(n+1).

From Emeric Deutsch, Feb 23 2004: (Start)

T(n, k) = Sum_{j=0..floor((n-k)/2)} (k-1+2*j)*binomial(2*n-k-1-2*j, n-1)/(2*n-k-1-2*j).

G.f.: t^2*z^2*C/( (1-z^2*C^2)*(1-t*z*C) ), where C = (1-sqrt(1-4*z))/(2*z) is the Catalan function. (End)

T(n,k) = A167772(n-1,k-1), k=2..n. - Reinhard Zumkeller, May 15 2014

From G. C. Greubel, May 26 2022: (Start)

T(n, n-1) = A000027(n-2).

T(n, n-2) = A000217(n-2).

T(n, n-3) = A166830(n-3). (End)

Extensions

More terms from Emeric Deutsch, Feb 23 2004