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,3

Links

Seiichi Manyama, Table of n, a(n) for n = 0..10000

Index entries for sequences related to groups

Formula

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

Example

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)

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

Prog

(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

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.

Sequence in context: A116634 A035960 A288254 * A065094 A145728 A145786

Adjacent sequences: A023890 A023891 A023892 * A023894 A023895 A023896

Keyword

nonn

Author

Olivier Gérard

Status

approved