A385408 -id:A385408 - cp's OEIS frontend

A381299 Irregular triangular array read by rows. T(n,k) is the number of ordered set partitions of [n] with exactly k descents, n>=0, 0<=k<=binomial(n,2).

1, 1, 2, 1, 4, 4, 4, 1, 8, 12, 18, 18, 12, 6, 1, 16, 32, 60, 84, 100, 92, 76, 48, 24, 8, 1, 32, 80, 176, 300, 448, 572, 650, 658, 596, 478, 334, 206, 102, 40, 10, 1, 64, 192, 480, 944, 1632, 2476, 3428, 4300, 5008, 5372, 5356, 4936, 4220, 3316, 2392, 1556, 904, 456, 188, 60, 12, 1

Offset: 0

Geoffrey Critzer, Feb 19 2025

Let p = ({b_1},{b_2},...,{b_m}) be an ordered set partition of [n] into m blocks for some m, 1<=m<=n. A descent in p is an ordered pair (x,y) in [n]X[n] such that x is in b_i, y is in b_j, iy.
T(n,binomial(n,2)) = 1 (counts the ordered set partition ({n},{n-1},...,{2},{1})).
For n>=1, T(n,0) = 2^(n-1).
Sum_{k>=0} T(n,k)*2^k = A289545(n).
Sum_{k>=0} T(n,k)*3^k = A347841(n).
Sum_{k>=0} T(n,k)*4^k = A347842(n).
Sum_{k>=0} T(n,k)*5^k = A347843(n).
Sum_{k>=0} T(n,k)*6^k = A385408(n).
Sum_{k>=0} T(n,k)*7^k = A347844(n).
Sum_{k>=0} T(n,k)*8^k = A347845(n).
Sum_{k>=0} T(n,k)*9^k = A347846(n).
T(n,k) is the number of preferential arrangements of n labeled elements with exactly k inversions. For example, there 4 preferential rearrangements of length 3 with 1 inversion: 132, 213, 212, 131. - Kyle Celano, Aug 18 2025

			Triangle T(n,k) begins:
  1;
  1;
  2,  1;
  4,  4,  4,  1;
  8, 12, 18, 18,  12,  6,  1;
 16, 32, 60, 84, 100, 92, 76, 48, 24, 8, 1;
 ...

Alois P. Heinz, Rows n = 0..50, flattened
Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 2019-2020.
Kyle Celano, Jennifer Elder, Kimberly P. Hadaway, Pamela E. Harris, Amanda Priestley, and Gabe Udell, Inversions in parking functions, arXiv:2508.11587 [math.CO], 2025. See Theorem 1.

Columns k=0-2 give: A011782, A001787(n-1) for n>=1, 2*A268586.
Cf. A000670 (row sums), A008302 (the cases where each block has size 1).
Cf. A125810, A161680, A240796, A289545, A347841, A347842, A347843, A347844, A347845, A347846, A385408.

b:= proc(o, u, t) option remember; expand(`if`(u+o=0, 1, `if`(t=1,
      b(u+o, 0$2), 0)+add(x^(u+j-1)*b(o-j, u+j-1, 1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..8);  # Alois P. Heinz, Feb 21 2025

nn = 7; B[n_] := FunctionExpand[QFactorial[n, u]]; e[z_] := Sum[z^n/B[n], {n, 0, nn}];Map[CoefficientList[#, u] &, Table[B[n], {n, 0, nn}] CoefficientList[Series[1/(1 -(e[z] - 1)), {z, 0, nn}], z]] // Grid

Sum_{k=0..binomial(n,2)} k * T(n,k) = A240796(n). - Alois P. Heinz, Feb 20 2025
T(n,k) is the coefficient of q^k in n!q times the coefficient of x^n in 1/(1- x - x^2/2!_q - x^3/3!_q - ...), where n!_q= 1*(1+q)*(1+q+q^2)*...*(1+q+...+q^(n-1)). - _Ira M. Gessel, Jun 24 2025
T(n,k) = Sum_{w} 2^(asc(w)), where w runs through the set of permutations with k inversions and asc(w) is the number of ascents of w. - Kyle Celano, Aug 18 2025

A381426 A(n,k) is the sum over all ordered partitions of [n] of k^j for an ordered partition with j inversions; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 13, 8, 1, 1, 5, 36, 75, 16, 1, 1, 6, 79, 696, 541, 32, 1, 1, 7, 148, 3851, 27808, 4683, 64, 1, 1, 8, 249, 14808, 567733, 2257888, 47293, 128, 1, 1, 9, 388, 44643, 5942608, 251790113, 369572160, 545835, 256, 1, 1, 10, 571, 113480, 40065301, 9546508128, 335313799327, 121459776768, 7087261, 512

Offset: 0

Alois P. Heinz, Feb 23 2025

			Square array A(n,k) begins:
   1,    1,       1,         1,          1,            1,             1, ...
   1,    1,       1,         1,          1,            1,             1, ...
   2,    3,       4,         5,          6,            7,             8, ...
   4,   13,      36,        79,        148,          249,           388, ...
   8,   75,     696,      3851,      14808,        44643,        113480, ...
  16,  541,   27808,    567733,    5942608,     40065301,     199246816, ...
  32, 4683, 2257888, 251790113, 9546508128, 179833594207, 2099255895008, ...

Alois P. Heinz, Antidiagonals n = 0..55, flattened
Wikipedia, Inversion
Wikipedia, Partition of a set

Columns k=0-9 give: A011782, A000670, A289545, A347841, A347842, A347843, A385408, A347844, A347845, A347846.
Main diagonal gives A381427.
Cf. A381299, A381369.

b:= proc(o, u, t, k) option remember; `if`(u+o=0, 1, `if`(t=1,
      b(u+o, 0$2, k), 0)+add(k^(u+j-1)*b(o-j, u+j-1, 1, k), j=1..o))
    end:
A:= (n, k)-> b(n, 0$2, k):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[o_, u_, t_, k_] := b[o, u, t, k] = If[u + o == 0, 1, If[t == 1, b[u + o, 0, 0, k], 0] + Sum[If[k == u + j - 1 == 0, 1, k^(u + j - 1)]*b[o - j, u + j - 1, 1, k], {j, 1, o}]];
A[n_, k_] := b[n, 0, 0, k];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Apr 19 2025, after Alois P. Heinz *)

A(n,k) = Sum_{j=0..binomial(n,2)} k^j * A381299(n,j).

cp's OEIS Frontend

A381299 Irregular triangular array read by rows. T(n,k) is the number of ordered set partitions of [n] with exactly k descents, n>=0, 0<=k<=binomial(n,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula