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

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

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

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

Crossrefs

Cf. A000166, A008289, A032020, A331517.

Cf. A161680, A369596.

Sequence in context: A168639 A275802 A218931 * A145734 A349729 A027936

Adjacent sequences: A331515 A331516 A331517 * A331519 A331520 A331521

Keyword

nonn

Author

Ilya Gutkovskiy, Jan 19 2020

Status

approved