|
|
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.)
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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).
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|