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

%I #28 Jun 01 2022 09:44:03

%S 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,

%T 1,808,622,379,193,82,28,7,1,2742,2120,1312,690,311,118,36,8,1,9458,

%U 7338,4596,2476,1164,474,163,45,9,1,33062,25724,16266,8928,4332,1856,692,218,55,10,1

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

%C A Riordan triangle.

%C Subtriangle of triangle in A167772. - _Philippe Deléham_, Nov 14 2009

%C 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

%H Reinhard Zumkeller, <a href="/A065602/b065602.txt">Rows n = 2..125 of triangle, flattened</a>

%H Emeric 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, 2) = A000958(n-1).

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

%F From _Emeric Deutsch_, Feb 23 2004: (Start)

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

%F 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)

%F T(n,k) = A167772(n-1,k-1), k=2..n. - _Reinhard Zumkeller_, May 15 2014

%F From _G. C. Greubel_, May 26 2022: (Start)

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

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

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

%e T(3,2)=1 reflecting the unique Dyck path (UUDUDD) of length 6, with no hills and height of first peak equal to 2.

%e Triangle begins:

%e 1;

%e 1, 1;

%e 3, 2, 1;

%e 8, 6, 3, 1;

%e 24, 18, 10, 4, 1;

%e 75, 57, 33, 15, 5, 1;

%e 243, 186, 111, 54, 21, 6, 1;

%e 808, 622, 379, 193, 82, 28, 7, 1;

%e 2742, 2120, 1312, 690, 311, 118, 36, 8, 1;

%p 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);

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

%o (Haskell)

%o a065602 n k = sum

%o [(k-1+2*j) * a007318' (2*n-k-1-2*j) (n-1) `div` (2*n-k-1-2*j) |

%o j <- [0 .. div (n-k) 2]]

%o a065602_row n = map (a065602 n) [2..n]

%o a065602_tabl = map a065602_row [2..]

%o -- _Reinhard Zumkeller_, May 15 2014

%o (SageMath)

%o 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) )

%o flatten([[T(n,k) for k in (2..n)] for n in (2..12)]) # _G. C. Greubel_, May 26 2022

%Y Row sums give A000957 (the Fine sequence).

%Y First column is A000958.

%Y Cf. A000108, A007318, A167772.

%K nonn,tabl,easy,nice

%O 2,4

%A _N. J. A. Sloane_, Dec 02 2001

%E More terms from _Emeric Deutsch_, Feb 23 2004