A114593 Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n, having k ascents of length at least 2 (1 <= k <= floor(n/2), n >= 2).

1, 2, 4, 2, 8, 10, 16, 36, 5, 32, 112, 42, 64, 320, 224, 14, 128, 864, 960, 168, 256, 2240, 3600, 1200, 42, 512, 5632, 12320, 6600, 660, 1024, 13824, 39424, 30800, 5940, 132, 2048, 33280, 119808, 128128, 40040, 2574, 4096, 78848, 349440, 489216, 224224, 28028, 429

Offset

2,2

Comments

Row n has floor(n/2) terms. Row sums are the Fine numbers (A000957). T(n,1) = 2^(n-2). T(n,2) = n(n-3)2^(n-5) (n>4) (2*A001793). T(2n,n) = Catalan(n). T(2n+1,n) = n*Catalan(n+1). Sum_{k=1..floor(n/2)} k*T(n,k) yields A114594.

T(n,k) is the number of permutations pi of [n-1] with k valleys such that s(pi) avoids the patterns 132, 231, and 312, where s is West's stack-sorting map. - Colin Defant, Sep 16 2018

Links

Table of n, a(n) for n=2..50.

Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.

Formula

T(n, k) = 2^(n-2k)*binomial(n+1, k)*binomial(n-k-1, k-1)/(n+1) (1 <= k <= floor(n/2)). G.f. = G-1, where G=G(t, z) satisfies z(2+tz)G^2 - (1+2z)G + 1 = 0.

Example

T(4,2)=2 because we have (UU)D(UU)DDD and (UU)DD(UU)DD, where U=(1,1), D=(1,-1) (ascents of length at least two are shown between parentheses).
Triangle starts:
   1;
   2;
   4,   2;
   8,  10;
  16,  36,   5;
  32, 112,  42;
  64, 320, 224,  14;

Maple

T:=proc(n, k) if k<=floor(n/2) then 2^(n-2*k)*binomial(n+1, k)*binomial(n-k-1, k-1)/(n+1) else 0 fi end: for n from 2 to 14 do seq(T(n, k), k=1..floor(n/2)) od;

Mathematica

m = 13(*rows*); G = 0; Do[G = Series[(1 + G^2 (2 + t z) z)/(1 + 2 z), {t, 0, m+1}, {z, 0, m+1}] // Normal // Expand, {m+2}]; Rest[CoefficientList[ #, t]]& /@ CoefficientList[G-1, z][[3;; ]] // Flatten (* Jean-François Alcover, Jan 22 2019 *)

Crossrefs

Cf. A000957, A001793, A114594.

Sequence in context: A303603 A308044 A319252 * A114655 A228890 A051288

Adjacent sequences: A114590 A114591 A114592 * A114594 A114595 A114596

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 11 2005

Status

approved