A381531 Number of permutations of [n] having the maximal possible number of pairs of integers i

1, 1, 2, 1, 4, 5, 2, 14, 34, 34, 12, 132, 540, 1020, 888, 288, 4608, 28800, 89280, 143712, 113472, 34560, 760320, 6773760, 31449600, 81527040, 117089280, 85847040, 24883200, 721612800, 8709120000, 56783462400, 217205452800, 495200563200, 651939840000, 450584985600, 125411328000

Offset: 0

Author

Alois P. Heinz, Feb 26 2025

Keywords

• nonn

Comments

The sequence has local minima at positions n in { A000217 }. The values at these positions are superfactorials (A000178).

Examples

			a(4) = 4: (1,4)(2)(3), (1,4)(2,3), (1,3,4)(2), (1,4,3)(2) with 2 pairs each.
a(6) = 2: (1,5,6)(2,4)(3), (1,6,5)(2,4)(3) with 7 pairs each.
		

Links

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

Crossrefs

Cf. A000178, A000217, A125811, A381529.

Programs

Maple

b:= proc(o, u, t) option remember; (p-> (d-> coeff(p, x, d)
      *x^d)(degree(p)))(expand(`if`(u+o=0, max(0, t-1)!,
      `if`(t>0, b(u+o, 0$2)*(t-1)!, 0)+add(x^(u+j-1)*
        b(o-j, u+j-1, t+1), j=`if`(t=0, 1, 1..o)))))
    end:
a:= n-> coeffs(b(n, 0$2)):
seq(a(n), n=0..36);

Formula

a(n) = A381529(n,A125811(n)-1).

a(A000217(n)) = A000178(n-1) for n>=1.