login
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
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
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
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Dec 11 2005
STATUS
approved