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

Author

Emeric Deutsch, Dec 01 2005

Keywords

• nonn
• tabf

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)

Examples

			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;
		

Links

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

Crossrefs

Cf. A000957, A000108, A114495.

Programs

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

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

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.