A246531 Number of endofunctions on [n] whose cycle lengths are divisors of n.

1, 1, 4, 18, 224, 1320, 42552, 262864, 12232320, 169594560, 6117023600, 61920993024, 8022787347456, 56694391376896, 5193025319432160, 174746314698336000, 10338252997184749568, 121439552019384139776, 26096843176349347142208, 262144006402373705728000

Offset

0,3

Links

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

Formula

a(n) = n! * [x^n] exp(Sum_{d|n} (-LambertW(-x))^d/d).

a(n) = A246522(n,n).

Maple

with(numtheory):
egf:= k-> exp(add((-LambertW(-x))^d/d, d=divisors(k))):
a:= n-> n!*coeff(series(egf(n), x, n+1), x, n):
seq(a(n), n=0..20);
# second Maple program:
with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1, k)*
      (i-1)!^j, j=0..`if`(irem(k, i)=0, n/i, 0))))
    end:
a:= n-> add(b(j$2, n)*n^(n-j)*binomial(n-1, j-1), j=0..n):
seq(a(n), n=0..20);

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0,
     Sum[multinomial[n, Join[{n - i*j},
     Table[i, {j}]]]/j!*b[n - i*j, i - 1, k]*(i - 1)!^j,
     {j, 0, If[Mod[k, i] == 0, n/i, 0]}]]];
a[n_] := If[n==0, 1, Sum[b[j, j, n]*n^(n-j)*Binomial[n-1, j-1], {j, 0, n}]];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 01 2022, after Alois P. Heinz *)

Crossrefs

Main diagonal of A246522.

Sequence in context: A071173 A143993 A145660 * A278565 A370189 A360283

Adjacent sequences: A246528 A246529 A246530 * A246532 A246533 A246534

Keyword

nonn

Author

Alois P. Heinz, Aug 28 2014

Status

approved