cp's OEIS Frontend

A002219 a(n) is the number of partitions of 2n that can be obtained by adding together two (not necessarily distinct) partitions of n.

%I A002219 M2574 N1018 #94 Sep 20 2023 14:37:46
%S A002219 1,3,6,14,25,53,89,167,278,480,760,1273,1948,3089,4682,7177,10565,
%T A002219 15869,22911,33601,47942,68756,96570,136883,189674,264297,362995,
%U A002219 499617,678245,924522,1243098,1676339,2237625,2988351,3957525,5247500,6895946,9070144,11850304
%N A002219 a(n) is the number of partitions of 2n that can be obtained by adding together two (not necessarily distinct) partitions of n.
%D A002219 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002219 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002219 Fausto A. C. Cariboni, <a href="/A002219/b002219.txt">Table of n, a(n) for n = 1..140</a> (terms 1..89 from Alois P. Heinz)
%H A002219 N. Metropolis and P. R. Stein, <a href="http://dx.doi.org/10.1016/S0021-9800(70)80091-6">An elementary solution to a problem in restricted partitions</a>, J. Combin. Theory, 9 (1970), 365-376.
%H A002219 Vladimir A. Shlyk, <a href="https://arxiv.org/abs/1805.07989">Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number</a>, arXiv:1805.07989 [math.CO], 2018.
%F A002219 See A213074 for Metropolis and Stein's formulas.
%F A002219 a(n) = A000041(2*n) - A006827(n) = A000041(2*n) - A046663(2*n,n).
%F A002219 a(n) = A276107(2*n). - _Max Alekseyev_, Oct 17 2022
%e A002219 Here are the seven partitions of 5: 1^5, 1^3 2, 1 2^2, 1^2 3, 2 3, 1 4, 5. Adding these together in pairs we get a(5) = 25 partitions of 10: 1^10, 1^8 2, 1^6 2^2, etc. (we get all partitions of 10 into parts of size <= 5 - there are 30 such partitions - except for five of them: we do not get 2 4^2, 3^2 4, 2^3 4, 1 3^3, 2^5). - _N. J. A. Sloane_, Jun 03 2012
%e A002219 From _Gus Wiseman_, Oct 27 2022: (Start)
%e A002219 The a(1) = 1 through a(4) = 14 partitions:
%e A002219   (11)  (22)    (33)      (44)
%e A002219         (211)   (321)     (422)
%e A002219         (1111)  (2211)    (431)
%e A002219                 (3111)    (2222)
%e A002219                 (21111)   (3221)
%e A002219                 (111111)  (3311)
%e A002219                           (4211)
%e A002219                           (22211)
%e A002219                           (32111)
%e A002219                           (41111)
%e A002219                           (221111)
%e A002219                           (311111)
%e A002219                           (2111111)
%e A002219                           (11111111)
%e A002219 (End)
%p A002219 g:= proc(n, i) option remember;
%p A002219      `if`(n=0, 1, `if`(i>1, g(n, i-1), 0)+`if`(i>n, 0, g(n-i, i)))
%p A002219     end:
%p A002219 b:= proc(n, i, s) option remember;
%p A002219      `if`(i=1 and s<>{} or n in s, g(n, i), `if`(i<1 or s={}, 0,
%p A002219       b(n, i-1, s)+ `if`(i>n, 0, b(n-i, i, map(x-> {`if`(x>n-i, NULL,
%p A002219       max(x, n-i-x)), `if`(x<i or x>n, NULL, max(x-i, n-x))}[], s)))))
%p A002219     end:
%p A002219 a:= n-> b(2*n, n, {n}):
%p A002219 seq(a(n), n=1..25);  # _Alois P. Heinz_, Jul 10 2012
%t A002219 b[n_, i_, s_] := b[n, i, s] = If[MemberQ[s, 0 | n], 0, If[n == 0, 1, If[i < 1, 0, b[n, i-1, s] + If[i <= n, b[n-i, i, Select[Flatten[Transpose[{s, s-i}]], 0 <= # <= n-i &]], 0]]]]; A006827[n_] := b[2*n, 2*n, {n}]; a[n_] := PartitionsP[2*n] - A006827[n]; Table[Print[an = a[n]]; an, {n, 1, 25}] (* _Jean-François Alcover_, Nov 12 2013, after _Alois P. Heinz_ *)
%t A002219 primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
%t A002219 subptns[s_]:=primeMS/@Divisors[Times@@Prime/@s];
%t A002219 Table[Length[Select[IntegerPartitions[2n],MemberQ[Total/@subptns[#],n]&]],{n,10}] (* _Gus Wiseman_, Oct 27 2022 *)
%o A002219 (Python)
%o A002219 from itertools import combinations_with_replacement
%o A002219 from sympy.utilities.iterables import partitions
%o A002219 def A002219(n): return len({tuple(sorted((p+q).items())) for p, q in combinations_with_replacement(tuple(Counter(p) for p in partitions(n)),2)}) # _Chai Wah Wu_, Sep 20 2023
%Y A002219 Column m=2 of A213086.
%Y A002219 Bisection of A276107.
%Y A002219 Cf. A064914, A000041, A002220, A002221, A002222, A213074, A006827, A046663.
%Y A002219 The strict version is A237258, ranked by A357854.
%Y A002219 Ranked by A357976 = positions of nonzero terms in A357879.
%Y A002219 A122768 counts distinct submultisets of partitions.
%Y A002219 A304792 counts subset-sums of partitions, positive A276024, strict A284640.
%Y A002219 Cf. A108917, A235130, A237194, A300061.
%K A002219 nonn,nice
%O A002219 1,2
%A A002219 _N. J. A. Sloane_
%E A002219 Better description from _Vladeta Jovovic_, Mar 06 2000
%E A002219 More terms from _Christian G. Bower_, Oct 12 2001
%E A002219 Edited by _N. J. A. Sloane_, Jun 03 2012
%E A002219 More terms from _Alois P. Heinz_, Jul 10 2012