A074759 Number of degree-n permutations of order dividing n. Number of solutions to x^n = 1 in S_n.

1, 1, 2, 3, 16, 25, 396, 721, 11264, 46089, 602200, 3628801, 133494912, 479001601, 7692266960, 95904273375, 1914926104576, 20922789888001, 628693317946656, 6402373705728001, 182635841123840000, 2496321046987530021, 55826951075231672512, 1124000727777607680001

Offset: 0

Author

Vladeta Jovovic, Sep 28 2002

Keywords

• easy
• nonn

Links

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

Crossrefs

Cf. A057731, A074351, A261431.

Main diagonal of A008307.

Programs

Maple

A:= proc(n,k) option remember; `if`(n<0, 0, `if`(n=0, 1,
       add(mul(n-i, i=1..j-1)*A(n-j,k), j=numtheory[divisors](k))))
    end:
a:= n-> A(n, n):
seq(a(n), n=0..25);  # Alois P. Heinz, Feb 14 2013

Mathematica

Table[a = Sum[x^i/i, {i, Divisors[n]}]; Part[Range[0, 20]! CoefficientList[Series[Exp[a], {x, 0, 20}], x],n + 1], {n, 0, 20}]  (* Geoffrey Critzer, Dec 04 2011 *)

Formula

a(n) = n! * [x^n] exp(Sum_{k divides n} x^k/k).

a(n) = Sum_{d|n} A057731(n,d) for n >= 1. - Alois P. Heinz, Jul 05 2021