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
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
- Alois P. Heinz, Table of n, a(n) for n = 0..483
- Wikipedia, Inversion
- Wikipedia, Permutation
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)