cp's OEIS Frontend

A074761 Number of partitions of n of order n.

%I A074761 #38 Jun 22 2025 16:27:42
%S A074761 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 A074761 1,11,9,13,494,1,10,13,423,1,981,1,137,115,12,1,1309,1,59,17,193,1,
%U A074761 240,21,1207,19,15,1,47274,1,16,239,1,25,3284,1,333,23,3731,1,42109,1,19
%N A074761 Number of partitions of n of order n.
%C A074761 Order of partition is lcm of its parts.
%C A074761 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 A074761 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 A074761 Coefficient of x^n in expansion of Sum_{i divides n} A008683(n/i)*1/Product_{j divides i} (1-x^j).
%e A074761 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 A074761 A:= proc(n)
%p A074761       uses numtheory;
%p A074761       local S;
%p A074761     S:= add(mobius(n/i)*1/mul(1-x^j,j=divisors(i)),i=divisors(n));
%p A074761     coeff(series(S,x,n+1),x,n);
%p A074761 end proc:
%p A074761 seq(A(n),n=1..100); # _Robert Israel_, Aug 06 2014
%t A074761 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 A074761 Table[Length[Select[IntegerPartitions[n],LCM@@#==n&]],{n,50}] (* _Gus Wiseman_, Aug 01 2018 *)
%o A074761 (PARI)
%o A074761 pr(k, x)={my(t=1); fordiv(k, d, t *= (1-x^d) ); return(t); }
%o A074761 a(n) =
%o A074761 {
%o A074761     my( x = 'x+O('x^(n+1)) );
%o A074761     polcoeff( Pol( sumdiv(n, i, moebius(n/i) / pr(i, x) ) ), n );
%o A074761 }
%o A074761 vector(66, n, a(n) )
%o A074761 \\ _Joerg Arndt_, Aug 06 2014
%Y A074761 Cf. A018818, A074351, A074752.
%Y A074761 Main diagonal of A256067, A256554.
%Y A074761 Cf. A000837, A074761, A285572, A290103, A305566, A316429, A316431, A316432, A316433, A317624.
%K A074761 easy,nonn
%O A074761 1,6
%A A074761 _Vladeta Jovovic_, Sep 28 2002