A074761 Number of partitions of n of order n.

1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 9, 1, 4, 5, 1, 1, 12, 1, 27, 7, 6, 1, 81, 1, 7, 1, 54, 1, 407, 1, 1, 11, 9, 13, 494, 1, 10, 13, 423, 1, 981, 1, 137, 115, 12, 1, 1309, 1, 59, 17, 193, 1, 240, 21, 1207, 19, 15, 1, 47274, 1, 16, 239, 1, 25, 3284, 1, 333, 23, 3731, 1, 42109, 1, 19

Offset

1,6

Comments

Order of partition is lcm of its parts.

a(n) is the number of conjugacy classes of the symmetric group S_n such that a representative of the class has order n. Here order means the order of an element of a group. Note that a(n) = 1 if and only if n is a prime power. - W. Edwin Clark, Aug 05 2014

Links

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 1..4000 (first 1025 terms from Joerg Arndt)

Formula

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

Example

The a(15) = 5 partitions are (15), (5,3,3,3,1), (5,5,3,1,1), (5,3,3,1,1,1,1), (5,3,1,1,1,1,1,1,1). - Gus Wiseman, Aug 01 2018

Maple

A:= proc(n)
      uses numtheory;
      local S;
    S:= add(mobius(n/i)*1/mul(1-x^j, j=divisors(i)), i=divisors(n));
    coeff(series(S, x, n+1), x, n);
end proc:
seq(A(n), n=1..100); # Robert Israel, Aug 06 2014

Mathematica

a[n_] := With[{s = Sum[MoebiusMu[n/i]*1/Product[1-x^j, {j, Divisors[i]}], {i, Divisors[n]}]}, SeriesCoefficient[s, {x, 0, n}]]; Array[a, 80}] (* Jean-François Alcover, Feb 29 2016 *)
Table[Length[Select[IntegerPartitions[n], LCM@@#==n&]], {n, 50}] (* Gus Wiseman, Aug 01 2018 *)

Prog

(PARI)
pr(k, x)={my(t=1); fordiv(k, d, t *= (1-x^d) ); return(t); }
a(n) =
{
    my( x = 'x+O('x^(n+1)) );
    polcoeff( Pol( sumdiv(n, i, moebius(n/i) / pr(i, x) ) ), n );
}
vector(66, n, a(n) )
\\ Joerg Arndt, Aug 06 2014

Crossrefs

Cf. A018818, A074351, A074752.

Main diagonal of A256067, A256554.

Cf. A000837, A074761, A285572, A290103, A305566, A316429, A316431, A316432, A316433, A317624.

Sequence in context: A254655 A344971 A077254 * A037861 A145037 A267115

Adjacent sequences: A074758 A074759 A074760 * A074762 A074763 A074764

Keyword

easy,nonn

Author

Vladeta Jovovic, Sep 28 2002

Status

approved