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

1, 1, 2, 3, 5, 7, 10, 14, 20, 27, 36, 48, 63, 82, 105, 134, 171, 215, 269, 335, 415, 511, 626, 764, 929, 1125, 1356, 1631, 1953, 2333, 2776, 3296, 3903, 4608, 5427, 6377, 7476, 8744, 10205, 11886, 13818, 16032, 18565, 21463, 24768, 28536

Offset: 0

Author

Olivier Gérard

Keywords

• nonn

Examples

			From _Gus Wiseman_, Jul 28 2022: (Start)
The a(0) = 1 through a(6) = 10 partitions:
  ()  (1)  (2)   (3)    (4)     (5)      (33)
           (11)  (21)   (22)    (32)     (42)
                 (111)  (31)    (41)     (51)
                        (211)   (221)    (222)
                        (1111)  (311)    (321)
                                (2111)   (411)
                                (11111)  (2211)
                                         (3111)
                                         (21111)
                                         (111111)
(End)
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..10000
• Index entries for sequences related to groups

Crossrefs

Cf. A009490, A023894 (first differences), A062297 (number of Abelian subgroups).

Cf. A018819, A062051, A131995.

The multiplicative version (factorizations) is A000688.

Not allowing 1's gives A023894, strict A054685, ranked by A355743.

The version for just primes (not prime-powers) is A034891, strict A036497.

The strict version is A106244.

These partitions are ranked by A302492.

A000041 counts partitions, strict A000009.

A001222 counts prime-power divisors.

A072233 counts partitions by sum and length.

A246655 lists the prime-powers (A000961 includes 1), towers A164336.

Cf. A001970, A055887, A063834, A085970, A279784, A295935, A356065.

Programs

Mathematica

Table[Length[Select[IntegerPartitions[n],Count[Map[Length,FactorInteger[#]], 1] == Length[#] &]], {n, 0, 35}] (* Geoffrey Critzer, Oct 25 2015 *)
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 *)

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

Python

from functools import lru_cache
from sympy import factorint
@lru_cache(maxsize=None)
def A023893(n):
    @lru_cache(maxsize=None)
    def c(n): return sum((p**(e+1)-p)//(p-1) for p,e in factorint(n).items())+1
    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

Formula

G.f.: (Product_{p prime} Product_{k>=1} 1/(1-x^(p^k))) / (1-x).