VOOZH about

URL: https://oeis.org/A391308

⇱ A391308 - OEIS

login
A391308
Triangle read by rows: T(n,k) is the number of linear intervals of height k in the weak order on permutations of length n (0 <= k < n).
3
1, 2, 1, 6, 6, 4, 24, 36, 32, 12, 120, 240, 240, 120, 48, 720, 1800, 1920, 1080, 576, 240, 5040, 15120, 16800, 10080, 6048, 3360, 1440, 40320, 141120, 161280, 100800, 64512, 40320, 23040, 10080, 362880, 1451520, 1693440, 1088640, 725760, 483840, 311040, 181440, 80640
OFFSET
1,2
COMMENTS
An interval is linear of height k if it is isomorphic to the total order on k+1 elements.
LINKS
Clément Chenevière, Enumerative study of intervals in lattices of Tamari type, Ph. D. thesis, Univ. Strasbourg (France), Ruhr-Univ. Bochum (Germany), HAL tel-04255439 [math.CO], 2024. See p. 145.
FORMULA
T(n,0) = n!.
T(n,1) = (n-1)*n!/2.
T(n,k) = 2*(n-k)*n!/(k+1) for k>1.
Row sums give A344216.
EXAMPLE
Triangle begins:
1;
2, 1;
6, 6, 4;
24, 36, 32, 12;
120, 240, 240, 120, 48;
720, 1800, 1920, 1080, 576, 240;
...
The T(4,3) = 12 linear intervals of height 3 in the weak order on S_4 are:
[1234, 4123] [1324, 4132] [3124, 4312] [1234, 2341]
[1243, 2431] [1423, 4231] [1324, 3241] [1342, 3421]
[1432, 4321] [2134, 4213] [2314, 4231] [3214, 4321]
MATHEMATICA
T[n_, k_]:=If[k==0, n!, If[k==1, (n-1)n!/2, 2(n-k)n!/(k+1)]]; Table[T[n, k], {n, 9}, {k, 0, n-1}]//Flatten (* Stefano Spezia, Dec 06 2025 *)
CROSSREFS
KEYWORD
nonn,tabl,easy
AUTHOR
Ludovic Schwob, Dec 06 2025
STATUS
approved