A114593 - OEIS

%I #13 Jan 22 2019 16:47:36

%S 1,2,4,2,8,10,16,36,5,32,112,42,64,320,224,14,128,864,960,168,256,

%T 2240,3600,1200,42,512,5632,12320,6600,660,1024,13824,39424,30800,

%U 5940,132,2048,33280,119808,128128,40040,2574,4096,78848,349440,489216,224224,28028,429

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

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

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

%H Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.

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

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

%e Triangle starts:

%e    1;

%e    2;

%e    4,   2;

%e    8,  10;

%e   16,  36,   5;

%e   32, 112,  42;

%e   64, 320, 224,  14;

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

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

%Y Cf. A000957, A001793, A114594.

%K nonn,tabf

%O 2,2

%A _Emeric Deutsch_, Dec 11 2005