A391308 - OEIS

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

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

An interval is linear of height k if it is isomorphic to the total order on k+1 elements.

LINKS

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

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:

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

Cf. A000142, A344216, A384133.

Sequence in context: A193561 A328349 A117965 * A111646 A363629 A342965

Adjacent sequences: A391305 A391306 A391307 * A391309 A391310 A391311

KEYWORD

nonn,tabl,easy

AUTHOR

Ludovic Schwob, Dec 06 2025

STATUS

approved