A023893 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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.