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

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

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.

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)

Example

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;

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

Prog

(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
(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

Crossrefs

Row sums give A000957 (the Fine sequence).

First column is A000958.

Cf. A000108, A007318, A167772.

Sequence in context: A193924 A110439 A327917 * A237596 A292898 A198498

Adjacent sequences: A065599 A065600 A065601 * A065603 A065604 A065605

Keyword

nonn,tabl,easy,nice

Author

N. J. A. Sloane, Dec 02 2001

Extensions

More terms from Emeric Deutsch, Feb 23 2004

Status

approved