A240796 -id:A240796 - 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

A240800 Total number of occurrences of the pattern 1<2<3 in all preferential arrangements (or ordered partitions) of n elements.

Original entry on oeis.org

0, 0, 1, 28, 570, 10700, 200235, 3857672, 77620788, 1641549000, 36576771165, 859032716740, 21251178078702, 553095031003060, 15122143306215855, 433634860865610320, 13020228528050054760, 408687299328542444880, 13389274565474007735009, 457150279686453405468780

Offset: 1

N. J. A. Sloane, Apr 13 2014

nonn

There are A000670(n) preferential arrangements of n elements - see A000670, A240763.

The number that avoid the pattern 1<2<3 is given in A226316.

Alois P. Heinz, Table of n, a(n) for n = 1..120

Cf. A000670, A240763, A240796-A240800, A226316.

b:= proc(n, t, h) option remember; `if`(n=0, [1, 0], add((p-> p+
      [0, p[1]*j*h/6])(b(n-j, t+j, h+j*t))*binomial(n, j), j=1..n))
    end:
a:= n-> b(n, 0$2)[2]:
seq(a(n), n=1..25);  # Alois P. Heinz, Dec 08 2014

b[n_, t_, h_] := b[n, t, h] = If[n == 0, {1, 0}, Sum[Function[{p}, p + {0, p[[1]]*j*h/6}][b[n - j, t + j, h + j*t]]*Binomial[n, j], {j, 1, n}]]; a[n_] := b[n, 0, 0][[2]]; Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Jun 08 2015, after Alois P. Heinz *)

a(n) ~ n! * n^3 / (72 * (log(2))^(n+1)). - Vaclav Kotesovec, May 03 2015

a(8)-a(20) from Alois P. Heinz, Dec 08 2014

A264082 Total number of inversions in all set partitions of [n].

Original entry on oeis.org

0, 0, 0, 1, 10, 74, 504, 3383, 23004, 160444, 1154524, 8594072, 66243532, 528776232, 4369175522, 37343891839, 329883579768, 3008985817304, 28312886239136, 274561779926323, 2741471453779930, 28159405527279326, 297291626845716642, 3223299667111201702

Offset: 0

Alois P. Heinz, Apr 03 2016

nonn

Each set partition is written as a sequence of blocks, ordered by the smallest elements in the blocks.

			a(3) = 1: one inversion in 13|2.
a(4) = 10: one inversion in each of 124|3, 13|24, 13|2|4, 1|24|3, and two inversions in each of 134|2, 14|23, 14|2|3.

Alois P. Heinz, Table of n, a(n) for n = 0..573
Wikipedia, Inversion (discrete mathematics)
Wikipedia, Partition of a set

Cf. A001809, A125810, A189052, A211606, A216239, A240796, A271370.

b:= proc(n, t) option remember; `if`(n=0, [1, 0], add((p-> p+
      [0, p[1]*(j*t/2)])(b(n-j, t+j-1))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 0)[2]:
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 20 2025

b[n_, t_] := b[n, t] = If[n == 0, {1, 0}, Sum[Function[p, p+{0, p[[1]]*(j*t/2)}][b[n-j, t+j-1]]*Binomial[n-1, j-1], {j, 1, n}]];
a[n_] := b[n, 0][[2]];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, May 21 2025, after Alois P. Heinz *)

a(n) = Sum_{k>0} k * A125810(n,k).

A240797 Total number of occurrences of the pattern 1=2 in all preferential arrangements (or ordered partitions) of n elements.

Original entry on oeis.org

0, 1, 9, 78, 750, 8115, 98343, 1324204, 19650060, 318926745, 5623615965, 107093749818, 2191142272410, 47944109702671, 1117341011896515, 27633982917342360, 722929036749464280, 19946727355457792853, 578926427416920550233, 17632301590672398115270

Offset: 1

N. J. A. Sloane, Apr 13 2014

nonn

There are A000670(n) preferential arrangements of n elements - see A000670, A240763.

The number that avoid the pattern 1=2 is n! (these are the permutations on n elements).

			The 13 preferential arrangements on 3 points and the number of times the pattern 1=2 occurs are:
1<2<3, 0
1<3<2, 0
2<1<3, 0
2<3<1, 0
3<1<2, 0
3<2<1, 0
1=2<3, 1
1=3<2, 1
2=3<1, 1
1<2=3, 1
2<1=3, 1
3<1=2, 1
1=2=3, 3,
for a total of a(3) = 9.

Alois P. Heinz, Table of n, a(n) for n = 1..420

Cf. A000670, A240763, A240796-A240800.

b:= proc(n) option remember; `if`(n=0, [1, 0], add((p-> p+
      [0, p[1]*j*(j-1)/2])(b(n-j))*binomial(n, j), j=1..n))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=1..25);  # Alois P. Heinz, Dec 08 2014

b[n_] := b[n] = If[n == 0, {1, 0}, Sum[Function[p, p + {0, p[[1]]*j*(j - 1)/2}][b[n - j]]*Binomial[n, j], {j, 1, n}]]; a[n_] := b[n][[2]]; Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Feb 07 2017, after Alois P. Heinz *)

a(n) ~ n! * n / (4 * (log(2))^n). - Vaclav Kotesovec, May 03 2015

a(8)-a(20) from Alois P. Heinz, Dec 08 2014

A240798 Total number of occurrences of the pattern 1=2=3 in all preferential arrangements (or ordered partitions) of n elements.

Original entry on oeis.org

0, 0, 1, 12, 130, 1500, 18935, 262248, 3972612, 65500200, 1169398065, 22494463860, 464072915878, 10225330604580, 239720548513355, 5959152063448080, 156592569864940040, 4337574220496785680, 126329273251232688069, 3859509516112803668220, 123426111134706786806890

Offset: 1

N. J. A. Sloane, Apr 13 2014

nonn

There are A000670(n) preferential arrangements of n elements - see A000670, A240763.

The number that avoid the pattern 1=2=3 is given in A080599.

Alois P. Heinz, Table of n, a(n) for n = 1..420

Cf. A000670, A240763, A240796-A240800, A080599.

b:= proc(n) option remember; `if`(n=0, [1, 0], add((p-> p+
      [0, p[1]*binomial(j, 3)])(b(n-j))*binomial(n, j), j=1..n))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=1..25);  # Alois P. Heinz, Dec 08 2014

b[n_] := b[n] = If[n==0, {1, 0}, Sum[Function[p, p+{0, p[[1]]*Binomial[j, 3]} ][b[n-j]]*Binomial[n, j], {j, 1, n}]]; a[n_] := b[n][[2]]; Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Feb 28 2017, after Alois P. Heinz *)

a(n) ~ n! * n / (12 * (log(2))^(n-1)). - Vaclav Kotesovec, May 03 2015

a(8)-a(21) from Alois P. Heinz, Dec 08 2014

A240799 Total number of occurrences of the pattern 1=2<3 in all preferential arrangements (or ordered partitions) of n elements.

Original entry on oeis.org

0, 0, 1, 20, 310, 4660, 72485, 1193080, 20938764, 392485560, 7850724915, 167242351100, 3785057708146, 90775554103052, 2301045251519105, 61499717442074800, 1729026306941190680, 51022485837639054768, 1577126907722325214959, 50967150013960792511700

Offset: 1

N. J. A. Sloane, Apr 13 2014

nonn

There are A000670(n) preferential arrangements of n elements - see A000670, A240763.

The number that avoid the pattern 1=2<3 is given in A001710 (1,3,12,60,360,...).

Alois P. Heinz, Table of n, a(n) for n = 1..420

Cf. A000670, A240763, A240796-A240800, A001710.

b:= proc(n, t) option remember; `if`(n=0, [1, 0], add((p-> p+
      [0, p[1]*j*(j-1)*t/6])(b(n-j, t+j))*binomial(n, j), j=1..n))
    end:
a:= n-> b(n, 0)[2]:
seq(a(n), n=1..25);  # Alois P. Heinz, Dec 08 2014

b[n_, t_] := b[n, t] = If[n==0, {1, 0}, Sum[Function[p, p+{0, p[[1]]*j*(j-1)*t/6}][b[n-j, t+j]]*Binomial[n, j], {j, 1, n}]]; a[n_] := b[n, 0][[2]]; Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Feb 28 2017, after Alois P. Heinz *)

a(n) ~ n! * n^2 / (24 * (log(2))^n). - Vaclav Kotesovec, May 03 2015

a(8)-a(20) from Alois P. Heinz, Dec 08 2014

A386011 Total number of inversions in all parking functions of length n.

Original entry on oeis.org

0, 1, 18, 300, 5400, 108045, 2408448, 59521392, 1620000000, 48230748225, 1560833556480, 54591962772204, 2053129541019648, 82648417236328125, 3546584706554265600, 161642713497024891840, 7799116552647941947392, 397183826482614347896737

Offset: 1

Kyle Celano, Jul 14 2025

			a(2)=1 because in the 3 parking functions of length 2 (11, 12, 21), there is 1 inversion: (1,2).

Kyle Celano, Table of n, a(n) for n = 1..100
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.
Richard P. Stanley, Parking Functions, 2011.
Wikipedia, Parking function.

Cf. A001809, A000272, A240796.

Table[Binomial[n,2] * n*(n+1)^(n-2)/2, {n, 0, 18}]

a(n) = binomial(n,2) * n*(n+1)^(n-2)/2.
a(n) = Sum_{k=0..binomial(n,2)} A152290(n,k)*k.
a(n) = binomial(n,2)*A055865(n)/2.

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

A240800 Total number of occurrences of the pattern 1<2<3 in all preferential arrangements (or ordered partitions) of n elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A264082 Total number of inversions in all set partitions of [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A240797 Total number of occurrences of the pattern 1=2 in all preferential arrangements (or ordered partitions) of n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A240798 Total number of occurrences of the pattern 1=2=3 in all preferential arrangements (or ordered partitions) of n elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A240799 Total number of occurrences of the pattern 1=2<3 in all preferential arrangements (or ordered partitions) of n elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A386011 Total number of inversions in all parking functions of length n.

Views

Author

Keywords

Examples

Links