A114494 - OEIS

%I #30 Sep 09 2024 22:43:16

%S 0,1,2,5,1,14,4,42,14,1,132,48,6,429,165,27,1,1430,572,110,8,4862,

%T 2002,429,44,1,16796,7072,1638,208,10,58786,25194,6188,910,65,1,

%U 208012,90440,23256,3808,350,12,742900,326876,87210,15504,1700,90,1,2674440,1188640

%N Triangle read by rows: T(n,k) is number of hill-free Dyck paths of semilength n and having k returns to the x-axis. (A Dyck path is said to be hill-free if it has no peaks at level 1.)

%C Row 1 contains one term; row n contains floor(n/2) terms (n >= 2). Row sums are the Fine numbers (A000957). Column 1 yields the Catalan numbers (n >= 2). Sum_{k=1..floor(n/2)} k*T(n,k) = A114495(n).

%C From _Colin Defant_, Sep 15 2018: (Start)

%C Let theta_{n-1,k-1} be the permutation k(k-1)...1(k+1)(k+2)...(n-1) obtained by concatenating the decreasing string k...1 with the increasing string (k+1)...(n-1). T(n,k) is the number of preimages of theta_{n-1,k-1} under West's stack-sorting map.

%C If pi is any permutation of [n-1] with exactly k-1 descents, then |s^{-1}(pi)| <= T(n,k), where s denotes West's stack-sorting map. (End)

%H C. Defant, <a href="https://arxiv.org/abs/1511.05681">Preimages under the stack-sorting algorithm</a>, arXiv:1511.05681 [math.CO], 2015-2018.

%H C. Defant, <a href="https://doi.org/10.1007/s00373-016-1752-5">Preimages under the stack-sorting algorithm</a>, Graphs Combin., 33 (2017), 103-122.

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

%H E. Deutsch and L. Shapiro, <a href="http://dx.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, k) = (k/(n-k))*binomial(2*n-2*k, n-2*k) (1 <= k <= floor(n/2)).

%F G.f.: 1/(1-tz^2*C^2)-1, where C=(1-sqrt(1-4z))/(2z) is the Catalan function.

%e T(5,2)=4 because we have UUD(D)UUDUD(D), UUD(D)UUUDD(D), UUDUD(D)UUD(D) and UUUDD(D)UUD(D), where U=(1,1), D=(1,-1) (returns to the axis are shown between parentheses).

%e Triangle starts:

%e     0;

%e     1;

%e     2;

%e     5,   1;

%e    14,   4;

%e    42,  14,   1;

%e   132,  48,   6;

%e   429, 165,  27,   1;

%p T:=proc(n,k) if k<=floor(n/2) then k*binomial(2*n-2*k,n-2*k)/(n-k) else 0 fi end: 0; for n from 2 to 15 do seq(T(n,k),k=1..floor(n/2)) od; # yields sequence in triangular form

%t Join[{0}, t[n_, k_]:=(k/(n - k)) Binomial [2 n - 2 k, n - 2 k]; Table[t[n, k], {n, 1, 20}, {k, n/2}]//Flatten] (* _Vincenzo Librandi_, Sep 15 2018 *)

%o (Magma) /* except 0 as triangle */ [[(k/(n-k))*Binomial(2*n-2*k, n-2*k): k in [1..n div 2]]: n in [2.. 15]]; // _Vincenzo Librandi_, Sep 15 2018

%Y Cf. A000957, A000108, A114495.

%K nonn,tabf

%O 1,3

%A _Emeric Deutsch_, Dec 01 2005