A089179 Number of equivalence classes of permutations of n letters, where the relation is that f and g are equivalent if every cycle of f is a power of some cycle of g.

1, 1, 2, 6, 20, 85, 402, 2464, 15752, 119655, 976190, 9331894, 91769988, 1077214879, 12570658310, 168390947820, 2337860163248, 35513649943201, 544140329564898, 9660558198790510, 166372364728477220, 3247358308730858301, 63714244306588584962, 1358307822841849329256

Offset

0,3

Links

Table of n, a(n) for n=0..23.

Albert Nijenhuis, Solution to Problem 5932, Amer. Math. Monthly, 82 (1975), pp. 86-87.

R. P. Stanley, Problem 5932, Amer. Math. Monthly, 80 (1973), p. 949.

Formula

E.g.f. x*exp(Sum( x^n/(n*phi(n)), n=1..infinity )) (phi is Euler's totient function). a(n) = n* A003510(n-1). - Vladeta Jovovic, Apr 15 2006

Mathematica

yy[nn_] := CoefficientList[Normal[Series[Exp[Sum[x^n t[n]/(n), {n, 1, nn}]], {x, 0, nn}]], x]; zz[nn_] := Table[Simplify[yy[nn][[m]] m! ], {m, 1, nn}]; zz[10] (* will then give the first 10 values *)

Crossrefs

Cf. A000142, A003510.

Sequence in context: A372987 A177480 A365229 * A177483 A004104 A304932

Adjacent sequences: A089176 A089177 A089178 * A089180 A089181 A089182

Keyword

easy,nonn,changed

Author

Herbert S. Wilf, Dec 08 2003

Extensions

More terms from Vladeta Jovovic, Apr 15 2006

a(0)=1 prepended by Alois P. Heinz, Jan 08 2025

Status

approved