cp's OEIS Frontend

A023893 Number of partitions of n into prime power parts (1 included); number of nonisomorphic Abelian subgroups of symmetric group S_n.

%I A023893 #55 Jul 15 2024 15:33:23
%S A023893 1,1,2,3,5,7,10,14,20,27,36,48,63,82,105,134,171,215,269,335,415,511,
%T A023893 626,764,929,1125,1356,1631,1953,2333,2776,3296,3903,4608,5427,6377,
%U A023893 7476,8744,10205,11886,13818,16032,18565,21463,24768,28536
%N A023893 Number of partitions of n into prime power parts (1 included); number of nonisomorphic Abelian subgroups of symmetric group S_n.
%H A023893 Seiichi Manyama, <a href="/A023893/b023893.txt">Table of n, a(n) for n = 0..10000</a>
%H A023893 <a href="/index/Gre#groups">Index entries for sequences related to groups</a>
%F A023893 G.f.: (Product_{p prime} Product_{k>=1} 1/(1-x^(p^k))) / (1-x).
%e A023893 From _Gus Wiseman_, Jul 28 2022: (Start)
%e A023893 The a(0) = 1 through a(6) = 10 partitions:
%e A023893   ()  (1)  (2)   (3)    (4)     (5)      (33)
%e A023893            (11)  (21)   (22)    (32)     (42)
%e A023893                  (111)  (31)    (41)     (51)
%e A023893                         (211)   (221)    (222)
%e A023893                         (1111)  (311)    (321)
%e A023893                                 (2111)   (411)
%e A023893                                 (11111)  (2211)
%e A023893                                          (3111)
%e A023893                                          (21111)
%e A023893                                          (111111)
%e A023893 (End)
%t A023893 Table[Length[Select[IntegerPartitions[n],Count[Map[Length,FactorInteger[#]], 1] == Length[#] &]], {n, 0, 35}] (* _Geoffrey Critzer_, Oct 25 2015 *)
%t A023893 nmax = 50; Clear[P]; P[m_] := P[m] = Product[Product[1/(1-x^(p^k)), {k, 1, m}], {p, Prime[Range[PrimePi[nmax]]]}]/(1-x)+O[x]^nmax // CoefficientList[ #, x]&; P[1]; P[m=2]; While[P[m] != P[m-1], m++]; P[m] (* _Jean-François Alcover_, Aug 31 2016 *)
%o A023893 (PARI) lista(m) = {x = t + t*O(t^m); gf = prod(k=1, m, if (isprimepower(k), 1/(1-x^k), 1))/(1-x); for (n=0, m, print1(polcoeff(gf, n, t), ", "));} \\ _Michel Marcus_, Mar 09 2013
%o A023893 (Python)
%o A023893 from functools import lru_cache
%o A023893 from sympy import factorint
%o A023893 @lru_cache(maxsize=None)
%o A023893 def A023893(n):
%o A023893     @lru_cache(maxsize=None)
%o A023893     def c(n): return sum((p**(e+1)-p)//(p-1) for p,e in factorint(n).items())+1
%o A023893     return (c(n)+sum(c(k)*A023893(n-k) for k in range(1,n)))//n if n else 1 # _Chai Wah Wu_, Jul 15 2024
%Y A023893 Cf. A009490, A023894 (first differences), A062297 (number of Abelian subgroups).
%Y A023893 Cf. A018819, A062051, A131995.
%Y A023893 The multiplicative version (factorizations) is A000688.
%Y A023893 Not allowing 1's gives A023894, strict A054685, ranked by A355743.
%Y A023893 The version for just primes (not prime-powers) is A034891, strict A036497.
%Y A023893 The strict version is A106244.
%Y A023893 These partitions are ranked by A302492.
%Y A023893 A000041 counts partitions, strict A000009.
%Y A023893 A001222 counts prime-power divisors.
%Y A023893 A072233 counts partitions by sum and length.
%Y A023893 A246655 lists the prime-powers (A000961 includes 1), towers A164336.
%Y A023893 Cf. A001970, A055887, A063834, A085970, A279784, A295935, A356065.
%K A023893 nonn
%O A023893 0,3
%A A023893 _Olivier Gérard_