A074064 Number of cycle types of degree-n permutations having the maximum possible order.

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 1, 1, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 2, 4, 1, 1, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 2, 4

Offset: 0

Author

Vladeta Jovovic, Sep 15 2002

Keywords

• easy
• nonn

Examples

			For n = 22 we have 4 such cycle types: [1, 1, 1, 3, 4, 5, 7], [1, 2, 3, 4, 5, 7], [3, 3, 4, 5, 7], [4, 5, 6, 7].
		

Links

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

Crossrefs

Cf. A000793, A074859, A256067, A256554.

Programs

Maple

A000793 := proc(n) option remember; local l,p,i ; l := 1: p := combinat[partition](n): for i from 1 to combinat[numbpart](n) do if ilcm( p[i][j] $ j=1..nops(p[i])) > l then l := ilcm( p[i][j] $ j=1..nops(p[i])) ; fi: od: RETURN(l) ; end proc:
taylInv := proc(i,n) local resul,j,idiv,k ; resul := 1 ; idiv := numtheory[divisors](i) ; for k from 1 to nops(idiv) do j := op(k,idiv) ; resul := resul*taylor(1/(1-x^j),x=0,n+1) ; resul := convert(taylor(resul,x=0,n+1),polynom) ; od ; coeftayl(resul,x=0,n) ; end proc:
A074064 := proc(n) local resul,a793,dvs,i,k ; resul := 0: a793 := A000793(n) ; dvs := numtheory[divisors](a793) ; for k from 1 to nops(dvs) do i := op(k,dvs) ; resul := resul+numtheory[mobius](a793/i)*taylInv(i,n) ; od : RETURN(resul) ; end proc: # R. J. Mathar, Mar 30 2007

Mathematica

b[n_, i_] := b[n, i] = Module[{p}, p = If[i < 1, 1, Prime[i]]; If[n == 0 || i < 1, 1, Max[b[n, i-1], Table[p^j*b[n-p^j, i-1], {j, 1, Log[p, n] // Floor}]]]];
g[n_] := g[n] = b[n, If[n < 8, 3, PrimePi[Ceiling[1.328*Sqrt[n*Log[n] // Floor]]]]];
a[n_] := a[n] = SeriesCoefficient[Sum[MoebiusMu[g[n]/i]/Product[1-x^j, {j, Divisors[i]}], {i, Divisors[g[n]]}] + O[x]^(n+1), n];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 100}] (* Jean-François Alcover, Apr 25 2017, after Alois P. Heinz *)

Formula

Coefficient of x^n in expansion of Sum_{i divides A000793(n)} mu(A000793(n)/i)*1/Product_{j divides i} (1-x^j).

Extensions

More terms from R. J. Mathar, Mar 30 2007

More terms from Sean A. Irvine, Oct 04 2011

More terms from Alois P. Heinz, Mar 29 2015