A372545 Number of permutations of [n] such that the number of cycles of length k is a multiple or a divisor of k for every k.

1, 1, 2, 6, 24, 120, 665, 4655, 37660, 345660, 3373629, 37109919, 443171498, 5761229474, 79709485141, 1199252731963, 19237203662248, 327101074802216, 5848216651372953, 111064609625430747, 2222478622302320382, 46709011248199791062, 1022898268873467547769

Offset: 0

Author

Alois P. Heinz, Jul 04 2024

Keywords

• nonn

Examples

			a(6) = 665 = 720 - 55 counts all permutations of [6] with the exception of 15 permutations of type (12)(34)(56) and 40 permutations of type (123)(456).
		

Links

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

Crossrefs

Cf. A372579, A374262, A374292, A374329.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0 or i=1, 1, add(`if`(
      irem(j, i)=0 or irem(i, j)=0, b(n-i*j, i-1)*(i-1)!^j/j!
      *combinat[multinomial](n, i$j, n-i*j), 0), j=0..n/i))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);