login
Number of different products of partitions of n; number of partitions of n into prime parts (1 included); number of distinct orders of Abelian subgroups of symmetric group S_n.
40

%I #63 Jun 24 2022 17:31:30

%S 1,1,2,3,4,6,8,11,14,18,23,29,36,45,55,67,81,98,117,140,166,196,231,

%T 271,317,369,429,496,573,660,758,869,993,1133,1290,1465,1662,1881,

%U 2125,2397,2699,3035,3407,3820,4276,4780,5337,5951,6628,7372,8191,9090

%N Number of different products of partitions of n; number of partitions of n into prime parts (1 included); number of distinct orders of Abelian subgroups of symmetric group S_n.

%C a(n) = length of n-th row in A212721. - _Reinhard Zumkeller_, Jun 14 2012

%C Number of partitions of n into noncomposite parts. - _Omar E. Pol_, Jun 23 2022

%H Alois P. Heinz, <a href="/A034891/b034891.txt">Table of n, a(n) for n = 0..10000</a> (terms n = 1..1000 from T. D. Noe)

%H <a href="/index/Par#part">Index entries for sequences related to partitions</a>

%F G.f.: (1/(1-x))*(1/Product_{k>0} (1-x^prime(k))). a(n) = (1/n)*Sum_{k=1..n} A074372(k)*a(n-k). Partial sums of A000607. - _Vladeta Jovovic_, Sep 19 2002

%F a(n) = A000041(n) - A353188(n). - _Omar E. Pol_, Jun 23 2022

%p b:= proc(n, i) option remember; `if`(n=0, 1, (p->

%p `if`(i<0, 0, b(n, i-1)+ `if`(p>n, 0,

%p b(n-p, i))))(`if`(i<1, 1, ithprime(i))))

%p end:

%p a:= n-> b(n, numtheory[pi](n)):

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Feb 15 2013

%t Table[ Length[ Union[ Apply[ Times, Partitions[ n], 1]]], {n, 30}]

%t CoefficientList[ Series[ (1/(1 - x)) Product[1/(1 - x^Prime[i]), {i, 100}], {x, 0, 50}], x] (* _Robert G. Wilson v_, Aug 17 2013 *)

%t b[n_, i_] := b[n, i] = Module[{p}, p = If[i<1, 1, Prime[i]]; If[n == 0, 1, If[i<0, 0, b[n, i-1] + If[p>n, 0, b[n-p, i]]]]]; a[n_] := b[n, PrimePi[n] ]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Nov 05 2015, after _Alois P. Heinz_ *)

%o (Haskell)

%o a034891 = length . a212721_row -- _Reinhard Zumkeller_, Jun 14 2012

%o (Sage) [Partitions(n, parts_in=(prime_range(n+1)+[1])).cardinality() for n in xsrange(1000)] # _Giuseppe Coppoletta_, Jul 11 2016

%Y Cf. A000041, A000792, A000793, A009490, A008578, A140436, A353188.

%K nonn,easy,nice

%O 0,3

%A _Wouter Meeussen_

%E More terms from _Vladeta Jovovic_

%E a(0)=1 from _Michael Somos_, Feb 05 2011