Voozh

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

(list; graph; refs; listen; history; text; internal format)

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