login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 20 02:34 EST 2019. Contains 329323 sequences. (Running on oeis4.)