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

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

Links

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

Wikipedia, Inversion

Wikipedia, Permutation

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)

Example

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

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

Crossrefs

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

Sequence in context: A309257 A135371 A086346 * A036290 A078904 A099012

Adjacent sequences: A337190 A337191 A337192 * A337194 A337195 A337196

Keyword

nonn

Author

Alois P. Heinz, Aug 18 2020

Status

approved