A331518 a(n) = Sum_{k=0..n} q(n,k) * !k, where q(n,k) = number of partitions of n into k distinct parts and !k = subfactorial of k.

1, 0, 0, 1, 1, 2, 4, 5, 7, 10, 21, 24, 37, 49, 71, 129, 160, 227, 313, 433, 572, 1012, 1213, 1750, 2315, 3223, 4159, 5740, 8945, 11206, 15402, 20506, 27545, 36068, 48122, 61960, 94694, 116240, 158580, 205397, 276458, 352526, 470101, 596433, 781224, 1111228

Offset: 0

Author

Ilya Gutkovskiy, Jan 19 2020

Keywords

• nonn

Comments

a(n) is the number of permutations of [n] whose fixed points sum to n*(n-1)/2. a(6) = 4: 143256, 231456, 312456, 523416. - Alois P. Heinz, Mar 02 2024

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A000166, A008289, A032020, A331517.

Cf. A161680, A369596.

Programs

Maple

g:= proc(n) option remember; `if`(n=0, 1, n*g(n-1)+(-1)^n) end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, g(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m+1)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..45);  # Alois P. Heinz, Mar 02 2024

Mathematica

Table[Sum[Length[Select[IntegerPartitions[n, {k}], UnsameQ @@ # &]] Subfactorial[k], {k, 0, n}], {n, 0, 45}]
nmax = 45; CoefficientList[Series[Sum[Subfactorial[k] x^(k (k + 1)/2)/Product[(1 - x^j), {j, 1, k}], {k, 0, nmax}], {x, 0, nmax}], x]
nmax = 50; CoefficientList[Series[Sum[Subfactorial[k] * x^(k*(k+1)/2) / Product[(1 - x^j), {j, 1, k}], {k, 0, Sqrt[2*nmax]}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Jan 28 2020 *)

Formula

G.f.: Sum_{k>=0} !k * x^(k*(k + 1)/2) / Product_{j=1..k} (1 - x^j).

a(n) = A369596(n,A161680(n)). - Alois P. Heinz, Mar 02 2024