A001809 -id:A001809 - cp's OEIS frontend

A055303 Number of labeled rooted trees with n nodes and 2 leaves.

3, 36, 360, 3600, 37800, 423360, 5080320, 65318400, 898128000, 13172544000, 205491686400, 3399953356800, 59499183744000, 1098446469120000, 21341245685760000, 435361411989504000, 9305850181275648000, 208013121699102720000, 4853639506312396800000

Offset: 3

Christian G. Bower, May 11 2000

a(n+1) is the sum of the zero moments over all permutations of n. E.g., a(4) is [1,2,3].[0,1,2] + [1,3,2].[0,1,2] + [2,1,3].[0,1,2] + [2,3,1].[0,1,2] + [3,1,2].[0,1,2] + [3,2,1].[0,1,2] = 8 + 7 + 7 + 5 + 5 + 4 = 36. - Jon Perry, Feb 20 2004

a(n) is the number of pairs of elements (p(i),p(j)) in an n-permutation such that i > j and p(i) < p(j) where j is not equal to i-1. Loosely speaking, we could say: the number of inversions that are not descents. A055303 + A001286 = A001809. For example, a(3)=3 from the permutations (given in one line notation): (2,3,1), (3,1,2), (3,2,1) we have the pairs (1,2), (2,3) and (1,3) respectively. - Geoffrey Critzer, Jan 06 2013

Index entries for sequences related to rooted trees

Column 2 of A055302.

Cf. A000217, A001754.

seq(n!*(n-2)*(n-1)/4, n = 3..21); # Zerinvary Lajos, Apr 25 2008 [corrected by Georg Fischer, Aug 17 2021]
f:= gfun:-rectoproc({(n-3)*a(n) - (n^2-n)*a(n-1), a(3)=3}, a(n), remember): map(f, [$3..20]); # Georg Fischer, Aug 17 2021

With[{nn=20}, Drop[CoefficientList[Series[x^3/(2(1-x)^3), {x,0,nn}], x] * Range[0,nn]!, 3]] (* Harvey P. Dale, Nov 22 2012 *)

E.g.f.: x^3/(2*(1-x)^3).
a(n) = (n-2)!*t(n-2)*t(n-1) = (n-2)!*(n-2)*(n-1)^2*n/4 = n!*(n-2)*(n-1)/4 = n!*t(n-2)/2 where t = A000217. - Jon Perry, Feb 22 2004
D-finite with recurrence: (n-3)*a(n) - (n^2 - n)*a(n-1) = 0. - Georg Fischer, Aug 17 2021
a(n) = 3 * A001754(n). - Alois P. Heinz, Aug 17 2021

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

A337193 Total number of inversions in all permutations of [n] where the descent set equals the subset of odd elements in [n-1].

Original entry on oeis.org

0, 0, 1, 3, 18, 80, 495, 2856, 20244, 142848, 1167885, 9729280, 90858438, 872361984, 9193900443, 99947258880, 1175452387560, 14270843322368, 185456745850329, 2487099677147136, 35413726451731770, 519907295578030080, 8052572864648861703, 128451121643116822528

Offset: 0

Alois P. Heinz, Aug 18 2020

nonn

			a(3) = 3, because in the A000111(3) = 2 permutations 213, 312 there are 3 inversions: (2,1), (3,1), (3,2).
a(4) = 18, because in the A000111(4) = 5 permutations 2143, 3142, 3241, 4132, 4231 there are 18 inversions: (2,1), (4,3), (3,1), (3,2), (4,2), (3,2), (3,1), (2,1), (4,1), (4,1), (4,3), (4,2), (3,2), (4,2), (4,3), (4,1), (2,1), (3,1).

Alois P. Heinz, Table of n, a(n) for n = 0..483
Wikipedia, Inversion
Wikipedia, Permutation

Cf. A000111, A001809, A211606, A216239, A337126.

b:= proc(u, o, t) option remember; `if`(u+o=0, [1, 0], add((p-> [0,
      `if`(t=0, o-1+j, u-j)*p[1]]+p)(b(o-1+j, u-j, 1-t)), j=1..u))
    end:
a:= n-> b(n, 0$2)[2]:
seq(a(n), n=0..30);

b[u_, o_, t_] := b[u, o, t] = Expand[If[u + o == 0, 1, Sum[x^If[t == 0, o - 1 + j, u - j]*b[o - 1 + j, u - j, 1 - t], {j, 1, u}]]];
a[n_] := With[{cc = CoefficientList[b[n, 0, 0], x]}, cc.Range[0, Length[cc]-1] ];
a /@ Range[0, 30] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz in A337126 *)

a(n) = Sum_{k=1..ceiling((n-1)^2/2)} k * A337126(n,k).
From Vaclav Kotesovec, Aug 31 2020: (Start)
a(n) ~ n! * 2^n * n^2 / Pi^(n+1).
a(n) ~ 2^(n + 1/2) * n^(n + 5/2) / (Pi^(n + 1/2) * exp(n)). (End)

A139365 Array of digit sums of factorial representation of numbers 0,1,...,n!-1 for n >= 1.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 1, 2, 2, 3, 0, 1, 1, 2, 2, 3, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 0, 1, 1, 2, 2, 3, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 4, 5, 5, 6, 6, 7, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7

Offset: 0

Wolfdieter Lang, May 21 2008

The row lengths sequence is A000142 (factorials).
When the factorial representation is read as (D. N.) Lehmer code for permutations of n objects then the digit sums in row n count the inversions of the permutations arranged in lexicographic order.
Row n is the first n! terms of A034968. - Franklin T. Adams-Watters, May 13 2009

			n=3: The Lehmer codes for the permutations of {1,2,3} are [0,0,0], [0,1,0], [1,0,0], [1,1,0], [2,0,0] and [2,1,0]. These are the factorial representations for 0,1,...,5=3!-1. Therefore row n=3 has the digit sums 0,1,1,2,2,3, the number of inversions of the permutations [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2] and [3,2,1] (lexicographic order).
Triangle begins:
  0;
  0;
  0, 1;
  0, 1, 1, 2, 2, 3;
  0, 1, 1, 2, 2, 3, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6;
  ...

Alois P. Heinz, Rows n = 0..8, flattened
FindStat - Combinatorial Statistic Finder, The number of inversions of a permutation
A. Kohnert, Kombinatorische Algorithmen in C, Skript, Uni Bayreuth, 1997, pp. 5-7 [Broken link]
Wolfdieter Lang, First 6 rows. Factorial representations or Lehmer code for permutations.
D. N. Lehmer, On the orderly listing of substitutions, Bull. AMS 12 (1906), 81-84.
Index entries for sequences related to factorial base representation

Cf. A034968. - Franklin T. Adams-Watters, May 13 2009
Cf. A008302.
Cf. A000142, A161680.
Row sums give A001809.

nn = 5; m = 1; While[Factorial@ m < nn! - 1, m++]; m; Table[Total@ IntegerDigits[k, MixedRadix[Reverse@ Range[2, m]]], {n, 0, 5}, {k, 0, n! - 1}] // Flatten (* Version 10.2, or *)
f[n_] := Block[{a = {{0, n}}}, Do[AppendTo[a, {First@ #, Last@ #} &@ QuotientRemainder[a[[-1, -1]], Times @@ Range[# - i]]], {i, 0, #}] &@ NestWhile[# + 1 &, 0, Times @@ Range[# + 1] <= n &]; Most@ Rest[a][[All, 1]]]; Table[Total@ f@ k, {n, 0, 5}, {k, 0, n! - 1}] // Flatten (* Michael De Vlieger, Aug 29 2016 *)

Row n >= 1: sum(facrep(n,m)[n-j],j=1..n), m=0,1,...,n!-1, with the factorial representation facrep(n,m) of m for given n.

T(n,n!-1) = A161680(n). - Alois P. Heinz, Jan 20 2025

Zeroth row added by Franklin T. Adams-Watters, May 13 2009

A227404 Total number of inversions in all permutations of order n consisting of a single cycle.

Original entry on oeis.org

0, 0, 1, 4, 22, 140, 1020, 8400, 77280, 786240, 8769600, 106444800, 1397088000, 19718899200, 297859161600, 4794806016000, 81947593728000, 1482030950400000, 28277150533632000, 567677135241216000, 11961768206868480000, 263969867887165440000

Offset: 0

Geoffrey Critzer, Sep 21 2013

nonn

The formula trivially follows from the observation that every pair of elements iMax Alekseyev, Jan 05 2018

a(n) is the number of ways to partition a (n+1)X(n+1) square, with the upper left hand corner missing, into ribbons of size n, see Alexandersson, Jordan. - Per W. Alexandersson, Jun 02 2020

			a(3) = 4 because the cyclic 3-permutations: (1,2,3), (1,3,2) written in one line (sequence) notation: {2,3,1}, {3,1,2} have 2 + 2 = 4 inversions.

Alois P. Heinz, Table of n, a(n) for n = 0..449
Per Alexandersson, Linus Jordan, Enumeration of border-strip decompositions, arXiv:1805.09778 [math.CO], 2018.
Per Alexandersson, Linus Jordan, Enumeration of border-strip decompositions, Journal of Integer Sequences, Vol. 22 (2019), Article 19.4.5.

Cf. A001809, A211606, A216239.

Table[Total[Map[Inversions,Map[FromCycles,Map[List, Map[Prepend[#,n]&, Permutations[n-1]]]]]],{n,1,8}]

For n>2, a(n) = n! * (3*n-1)/12. - Vaclav Kotesovec, Feb 14 2014

a(13)-a(15) from Alois P. Heinz, Sep 26 2013

Terms a(16) and beyond from Max Alekseyev, Jan 05 2018

A271372 Total number of inversions in all compositions of n into distinct parts.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 11, 12, 21, 31, 112, 122, 212, 294, 456, 1147, 1381, 2144, 3059, 4494, 6081, 13597, 15928, 24716, 33728, 49260, 65016, 93229, 169249, 210206, 304979, 417600, 584037, 779731, 1076824, 1409102, 2418068, 2950722, 4213584, 5581351, 7779829

Offset: 0

Alois P. Heinz, Apr 05 2016

nonn

			a(3) = 1: 21.
a(4) = 1: 31.
a(5) = 2: 41, 32.
a(6) = 11: one inversion in each of 51, 132, 42, 213, two inversions in each of 231, 312, three inversions in 321.

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

Cf. A001809, A008289, A032020, A189052, A271371.

b:= proc(n, i, t) option remember; `if`(n>i*(i+1)/2, 0,
      `if`(n=0, t!*t*(t-1)/4, b(n, i-1, t)+
      `if`(i>n, 0, b(n-i, i-1, t+1))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..60);

b[n_, i_, t_] := b[n, i, t] = If[n > i*(i + 1)/2, 0, If[n == 0, t!*t*(t - 1)/4, b[n, i - 1, t] + If[i > n, 0, b[n - i, i - 1, t + 1]]]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, May 29 2018, from Maple *)

a(n) = Sum_{k>=1} A001809(k) * A008289(n,k).

A335345 Expansion of e.g.f. exp(x^2/(2*(1 - x)^3)).

Original entry on oeis.org

1, 0, 1, 9, 75, 690, 7305, 89145, 1237425, 19221300, 329371245, 6157738125, 124551652995, 2707913238030, 62945320162725, 1557291398788125, 40844991621859425, 1131753403094113800, 33025920511859300025, 1012128709342410284625, 32494107983067177522075

Offset: 0

Ilya Gutkovskiy, Jun 02 2020

nonn

Cf. A001809, A091695, A185369, A335344.

nmax = 20; CoefficientList[Series[Exp[x^2/(2 (1 - x)^3)], {x, 0, nmax}], x] Range[0, nmax]!
a[0] = 1; a[n_] := a[n] = (1/4) Sum[Binomial[n - 1, k - 1] k (k - 1) k! a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 20}]

seq(n)=Vec(serlaplace(exp(x^2/(2*(1 - x)^3) + O(x*x^n)))) \\ Andrew Howroyd, Jun 02 2020

a(0) = 1; a(n) = Sum_{k=1..n} binomial(n-1,k-1) * A001809(k) * a(n-k).
D-finite with recurrence 2*a(n) +8*(-n+1)*a(n-1) +2*(n-1)*(6*n-13)*a(n-2) -(n-1)*(n-2)*(8*n-23)*a(n-3) +2*(n-1)*(n-2)*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jun 05 2020
a(n) ~ 2^(-9/8) * 3^(1/8) * n^(n - 1/8) * exp(1/54 - n^(1/4)/(2^(15/4)*3^(5/4)) - sqrt(6*n)/12 + 2^(7/4)*3^(-3/4)*n^(3/4) - n). - Vaclav Kotesovec, Jun 11 2020
a(n) = n! * Sum_{k=0..floor(n/2)} binomial(n+k-1,n-2*k)/(2^k * k!). - Seiichi Manyama, Jun 17 2024

A368342 Sum of digits of the numbers 0..n-1 in factorial base (A108731).

Original entry on oeis.org

0, 0, 1, 2, 4, 6, 9, 10, 12, 14, 17, 20, 24, 26, 29, 32, 36, 40, 45, 48, 52, 56, 61, 66, 72, 73, 75, 77, 80, 83, 87, 89, 92, 95, 99, 103, 108, 111, 115, 119, 124, 129, 135, 139, 144, 149, 155, 161, 168, 170, 173, 176, 180, 184, 189, 192, 196, 200, 205, 210, 216

Offset: 0

Kevin Ryde, Dec 30 2023

Trollope considers sums of digits in a mixed-radix representation and the present sequence is a(n) = Trollope's A(n) for the case xi_i = i+1.

			For n=8, the factorial-base representations of 0..7 are 0, 1, 10, 11, 20, 21, 100, 101 and their total sum of digits is a(8) = 12.

Kevin Ryde, Table of n, a(n) for n = 0..10000
Kevin Ryde, PARI/GP Code.
J. R. Trollope, Generalized Bases and Digital Sums, American Mathematical Monthly, volume 74, number 6, July 1967, pp. 690-694.
Index entries for sequences related to factorial base representation.

Cf. A007623, A108731 (factorial base), A301652 (reversed), A084558 (length), A034968 (digit sum).

Cf. A001809.

s[n_] := Module[{k = n, m = 2, r, s = {}}, While[{k, r} = QuotientRemainder[k, m]; k != 0 || r != 0, AppendTo[s, r]; m++]; Total[s]]; Join[{0}, Accumulate[Array[s, 100, 0]]] (* Amiram Eldar, Mar 11 2024 *)

PARI
```
\\ See links.
```

a(n) = Sum_{i=0..n-1} A034968(i).
a(n) = Sum_{j=1..k} d[j] * (s(j) + d[j]/2 + (j-2)*(j+1)/4) * j!, where d[j] = A301652(n,j) are the factorial-base digits n = Sum_{j=1..k} d[j]*j!, where k = A084558(n), and digit sum s(j) = Sum_{i=j+1..k} d[i].
a(n) ~ (1/4)*n*k^2 where k = A084558(n), from the j=k term in the above sum.
a(n) = a(n-k!) + n-k! + k!*k*(k-1)/4, for k! <= n < (k+1)!, which is k = A084558(n).
a(k!) = k! * k*(k-1)/4 = A001809(k).

A202363 Triangular array read by rows: T(n,k) is the number of inversion pairs ( p(i) < p(j) with i>j ) that are separated by exactly k elements in all n-permutations (where the permutation is represented in one line notation); n>=2, 0<=k<=n-2.

Original entry on oeis.org

1, 6, 3, 36, 24, 12, 240, 180, 120, 60, 1800, 1440, 1080, 720, 360, 15120, 12600, 10080, 7560, 5040, 2520, 141120, 120960, 100800, 80640, 60480, 40320, 20160, 1451520, 1270080, 1088640, 907200, 725760, 544320, 362880, 181440, 16329600, 14515200, 12700800, 10886400, 9072000, 7257600, 5443200, 3628800, 1814400

Offset: 2

Geoffrey Critzer, Jan 09 2013

Row sums = A001809.

Column for k = 0 is A001286.

			T(3,1) = 3 because from the permutations (given in one line notation): (2,3,1), (3,1,2), (3,2,1) we have respectively 3 inversion pairs (1,2), (2,3) and (1,3) which are all separated by 1 element.
Triangle T(n,k) begins:
       1;
       6,      3;
      36,     24,     12;
     240,    180,    120,    60;
    1800,   1440,   1080,   720,   360;
   15120,  12600,  10080,  7560,  5040,  2520;
  141120, 120960, 100800, 80640, 60480, 40320, 20160;
  ...

Alois P. Heinz, Rows n = 2..142, flattened

Cf. A001286, A001809, A055303.

nn=10;Range[0,nn]!CoefficientList[Series[x^2/2/(1-x)^2/(1-y x),{x,0,nn}],{x,y}]//Grid

E.g.f.: x^2/2 * (1/(1-x)^2)* (1/(1-y*x)).

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

A055303 Number of labeled rooted trees with n nodes and 2 leaves.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A337193 Total number of inversions in all permutations of [n] where the descent set equals the subset of odd elements in [n-1].

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A139365 Array of digit sums of factorial representation of numbers 0,1,...,n!-1 for n >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A227404 Total number of inversions in all permutations of order n consisting of a single cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A271372 Total number of inversions in all compositions of n into distinct parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A335345 Expansion of e.g.f. exp(x^2/(2*(1 - x)^3)).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

A368342 Sum of digits of the numbers 0..n-1 in factorial base (A108731).