login
Number of partitions of n of order n.
37

%I #34 Aug 03 2018 08:16:05

%S 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,

%T 1,11,9,13,494,1,10,13,423,1,981,1,137,115,12,1,1309,1,59,17,193,1,

%U 240,21,1207,19,15,1,47274,1,16,239,1,25,3284,1,333,23,3731,1,42109,1,19

%N Number of partitions of n of order n.

%C Order of partition is lcm of its parts.

%C 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

%H Joerg Arndt and Alois P. Heinz, <a href="/A074761/b074761.txt">Table of n, a(n) for n = 1..4000</a> (first 1025 terms from Joerg Arndt)

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

%e 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

%p A:= proc(n)

%p uses numtheory;

%p local S;

%p S:= add(mobius(n/i)*1/mul(1-x^j,j=divisors(i)),i=divisors(n));

%p coeff(series(S,x,n+1),x,n);

%p end proc:

%p seq(A(n),n=1..100); # _Robert Israel_, Aug 06 2014

%t 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 *)

%t Table[Length[Select[IntegerPartitions[n],LCM@@#==n&]],{n,50}] (* _Gus Wiseman_, Aug 01 2018 *)

%o (PARI)

%o pr(k, x)={my(t=1); fordiv(k, d, t *= (1-x^d) ); return(t); }

%o a(n) =

%o {

%o my( x = 'x+O('x^(n+1)) );

%o polcoeff( Pol( sumdiv(n, i, moebius(n/i) / pr(i, x) ) ), n );

%o }

%o vector(66, n, a(n) )

%o \\ _Joerg Arndt_, Aug 06 2014

%Y Cf. A018818, A074351, A074752.

%Y Main diagonal of A256067, A256554.

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

%K easy,nonn

%O 1,6

%A _Vladeta Jovovic_, Sep 28 2002