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

Links

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

Wikipedia, Permutation

Example

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

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

Crossrefs

Cf. A372579, A374262, A374292, A374329.

Sequence in context: A152343 A177529 A138619 * A189841 A189256 A152344

Adjacent sequences: A372541 A372542 A372544 * A372546 A372547 A372548

Keyword

nonn

Author

Alois P. Heinz, Jul 04 2024

Status

approved