A390553 Total number of permutations of [k] having exactly n cycles with cycle length set [m] for nonnegative integers k and m.

1, 1, 4, 142, 163541, 11402245766, 73126631811200332, 61813796692992154901350387, 9377589491378940028767495513551218152, 333878364642348231785641974791552269083712281908056, 3534887605489498667394663017655202046325566383504435047753396139331

Offset

0,3

Comments

The values of k and m can be restricted: n <= k <= n*(n+1)/2 and 0 <= m <= n. Other values do not contribute positively. Note that [0] = {}, [1] = {1}, [k] = {1..k}.

Links

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

Wikipedia, Permutation

Formula

a(n) = Sum_{k=n..n*(n+1)/2} A392215(k,n).

Example

a(2) = 4: (1)(2), (1)(23), (13)(2), (12)(3).

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, add(expand(b(n-i*j, i+1))*
      x^j*combinat[multinomial](n, n-i*j, i$j)/j!*(i-1)!^j, j=1..n/i))
    end:
a:= n-> add(coeff(b(k, 1), x, n), k=n..n*(n+1)/2):
seq(a(n), n=0..10);

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[Expand[b[n-i*j, i+1]]*x^j*Multinomial@@Join[{n-i*j}, Table[i, {j}]]/j!*(i-1)!^j, {j, 1, n/i}]];
a[n_] := Sum[Coefficient[b[k, 1], x, n], {k, n, n(n+1)/2}];
Table[a[n], {n, 0, 10}] (* Jean-François Alcover, Feb 17 2026, after Alois P. Heinz *)

Crossrefs

Column sums of A392215.

Cf. A000110, A000217.

Sequence in context: A299833 A231949 A239248 * A225133 A122422 A307703

Adjacent sequences: A390550 A390551 A390552 * A390554 A390555 A390556

Keyword

nonn

Author

Alois P. Heinz, Feb 03 2026

Status

approved