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,3

Comments

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, i<j, and x>y.

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

Links

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.

Formula

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

Example

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

Maple

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

Mathematica

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

Crossrefs

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.

Sequence in context: A393443 A140946 A008741 * A369999 A110316 A111975

Adjacent sequences: A381296 A381297 A381298 * A381300 A381301 A381302

Keyword

nonn,tabf

Author

Geoffrey Critzer, Feb 19 2025

Status

approved