A114494 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.)

0, 1, 2, 5, 1, 14, 4, 42, 14, 1, 132, 48, 6, 429, 165, 27, 1, 1430, 572, 110, 8, 4862, 2002, 429, 44, 1, 16796, 7072, 1638, 208, 10, 58786, 25194, 6188, 910, 65, 1, 208012, 90440, 23256, 3808, 350, 12, 742900, 326876, 87210, 15504, 1700, 90, 1, 2674440, 1188640

Offset

1,3

Comments

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

From Colin Defant, Sep 15 2018: (Start)

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.

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)

Links

Table of n, a(n) for n=1..52.

C. Defant, Preimages under the stack-sorting algorithm, arXiv:1511.05681 [math.CO], 2015-2018.

C. Defant, Preimages under the stack-sorting algorithm, Graphs Combin., 33 (2017), 103-122.

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

E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

Formula

T(n, k) = (k/(n-k))*binomial(2*n-2*k, n-2*k) (1 <= k <= floor(n/2)).

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

Example

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).
Triangle starts:
    0;
    1;
    2;
    5,   1;
   14,   4;
   42,  14,   1;
  132,  48,   6;
  429, 165,  27,   1;

Maple

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

Mathematica

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

Prog

(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 *)

Crossrefs

Cf. A000957, A000108, A114495.

Sequence in context: A352577 A263487 A101920 * A118964 A263771 A073187

Adjacent sequences: A114491 A114492 A114493 * A114495 A114496 A114497

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 01 2005

Status

approved