cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-5 of 5 results.

A211606 Total number of inversions over all involutions of length n.

Original entry on oeis.org

0, 0, 1, 5, 26, 110, 490, 2086, 9240, 40776, 185820, 855580, 4048616, 19455800, 95773496, 479581480, 2454041920, 12776826816, 67849286160, 366455145936, 2015621873440, 11268605368160, 64074235576736, 370040657037920, 2171138049287296, 12928631894588800, 78139702237771200
Offset: 0

Views

Author

Geoffrey Critzer, Feb 10 2013

Keywords

Examples

			a(3) = 5 because in the involutions of {1,2,3}: (given in word form) 213, 321, 132, 123, there are respectively 1 + 3 + 1 + 0 = 5 inversions.

References

  • R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 339.

Links

Crossrefs

Cf. A000085, A001809, A161124, A216239, A337193.

Programs

  • Maple
    a:= proc(n) option remember; `if`(n<3, n*(n-1)/2,
      n*((n-2)*(9*n-7) *a(n-1) +(n-1)*(9*n^2-13*n+2) *a(n-2))/
      ((n-2)*(9*n^2-31*n+24)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 12 2013
  • Mathematica
    (* first do *) Needs["Combinatorica`"] // Quiet (* then *)
Table[Total[Map[Inversions, Involutions[n]]], {n, 0, 10}]
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (x^2/2 + x^3/3 + x^4/4) Exp[x + x^2/2], {x, 0, n}]]; (* Michael Somos, Jun 03 2019 *)
  • PARI
    {a(n) = if( n<0, 0, n! * polcoeff( (x^2/2 + x^3/3 + x^4/4) * exp(x + x^2/2 + x * O(x^n)), n))}; /* Michael Somos, Jun 03 2019 */

Formula

From Alois P. Heinz, Feb 12 2013: (Start)
a(n) = a(n-1) + (n-1)*a(n-2) + A000085(n-2)*(n-1)^2 for n>1; a(0) = a(1) = 0.
a(n) = (n*(n-2)*(9*n-7) *a(n-1) +n*(n-1)*(9*n^2-13*n+2) *a(n-2))/ ((n-2)*(9*n^2-31*n+24)) for n>=3; a(n) = n*(n-1)/2 for n<3.
E.g.f.: (x^2/2 + x^3/3 + x^4/4) * exp(x + x^2/2).
(End)
a(n) ~ sqrt(2)/8 * n^(n/2+2)*exp(sqrt(n)-n/2-1/4) * (1-3/(8*sqrt(n))). - Vaclav Kotesovec, Aug 15 2013

Extensions

a(13)-a(15) from Alois P. Heinz, Feb 10 2013
Further terms from Alois P. Heinz, Feb 12 2013

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

Views

Author

Alois P. Heinz, Apr 03 2016

Keywords

Comments

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

Examples

			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.

Links

Crossrefs

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

Programs

  • Maple
    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
  • Mathematica
    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 *)

Formula

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

Views

Author

Alois P. Heinz, Aug 18 2020

Keywords

Examples

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

Links

Crossrefs

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

Programs

  • Maple
    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);
  • Mathematica
    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 *)

Formula

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)

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

Views

Author

Geoffrey Critzer, Sep 21 2013

Keywords

Comments

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

Examples

			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.

Links

Crossrefs

Cf. A001809, A211606, A216239.

Programs

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

Formula

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

Extensions

a(13)-a(15) from Alois P. Heinz, Sep 26 2013
Terms a(16) and beyond from Max Alekseyev, Jan 05 2018

A228924 Irregular triangular array read by rows: T(n,k) is the number of derangement permutations of [n] that have exactly k inversions; n>=2, 1<=k<=binomial(n,2) for even n, 1<=k<=binomial(n,2)-1 for odd n.

Original entry on oeis.org

1, 0, 2, 0, 1, 4, 1, 2, 1, 0, 0, 4, 8, 4, 10, 10, 6, 2, 0, 0, 1, 12, 18, 16, 35, 44, 47, 40, 25, 14, 8, 4, 1, 0, 0, 0, 6, 32, 44, 60, 118, 160, 208, 244, 244, 214, 174, 140, 104, 64, 30, 10, 2, 0, 0, 0, 1, 24, 83, 118, 206, 388, 565, 802, 1068, 1308, 1466, 1508, 1479, 1414, 1290, 1076, 806, 544, 333, 186, 96, 46, 19, 6, 1
Offset: 2

Views

Author

Geoffrey Critzer, Sep 08 2013

Keywords

Comments

Row sums = A000166.
Sum_{k>=1} T(n,k)*k = A216239(n).
Sum_{even k} T(n,k) = A003221(n) and Sum_{odd k} T(n,k) = A000387(n).
It would be nice to have a closed formula for T(n,k). - Alois P. Heinz, Dec 31 2014

Examples

			Triangle T(n,k) begins:
  1;
  0, 2;
  0, 1, 4,  1,  2,  1;
  0, 0, 4,  8,  4, 10, 10,  6,  2;
  0, 0, 1, 12, 18, 16, 35, 44, 47, 40, 25, 14, 8, 4, 1;
  ...

Links

Crossrefs

Cf. A000166, A000387, A003221, A008302, A216239.

Programs

  • Mathematica
    Map[Distribution[#,Range[1,Max[#]]]&,Table[Map[Inversions,Derangements[n]],{n,2,6}]]//Grid
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.