login
a(n) is the number of partitions of 2n that can be obtained by adding together two (not necessarily distinct) partitions of n.
(Formerly M2574 N1018)
62

%I M2574 N1018 #94 Sep 20 2023 14:37:46

%S 1,3,6,14,25,53,89,167,278,480,760,1273,1948,3089,4682,7177,10565,

%T 15869,22911,33601,47942,68756,96570,136883,189674,264297,362995,

%U 499617,678245,924522,1243098,1676339,2237625,2988351,3957525,5247500,6895946,9070144,11850304

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 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 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 See A213074 for Metropolis and Stein's formulas.

%F a(n) = A000041(2*n) - A006827(n) = A000041(2*n) - A046663(2*n,n).

%F a(n) = A276107(2*n). - _Max Alekseyev_, Oct 17 2022

%e 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 From _Gus Wiseman_, Oct 27 2022: (Start)

%e The a(1) = 1 through a(4) = 14 partitions:

%e (11) (22) (33) (44)

%e (211) (321) (422)

%e (1111) (2211) (431)

%e (3111) (2222)

%e (21111) (3221)

%e (111111) (3311)

%e (4211)

%e (22211)

%e (32111)

%e (41111)

%e (221111)

%e (311111)

%e (2111111)

%e (11111111)

%e (End)

%p g:= proc(n, i) option remember;

%p `if`(n=0, 1, `if`(i>1, g(n, i-1), 0)+`if`(i>n, 0, g(n-i, i)))

%p end:

%p b:= proc(n, i, s) option remember;

%p `if`(i=1 and s<>{} or n in s, g(n, i), `if`(i<1 or s={}, 0,

%p b(n, i-1, s)+ `if`(i>n, 0, b(n-i, i, map(x-> {`if`(x>n-i, NULL,

%p max(x, n-i-x)), `if`(x<i or x>n, NULL, max(x-i, n-x))}[], s)))))

%p end:

%p a:= n-> b(2*n, n, {n}):

%p seq(a(n), n=1..25); # _Alois P. Heinz_, Jul 10 2012

%t 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 primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

%t subptns[s_]:=primeMS/@Divisors[Times@@Prime/@s];

%t Table[Length[Select[IntegerPartitions[2n],MemberQ[Total/@subptns[#],n]&]],{n,10}] (* _Gus Wiseman_, Oct 27 2022 *)

%o (Python)

%o from itertools import combinations_with_replacement

%o from sympy.utilities.iterables import partitions

%o 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 Column m=2 of A213086.

%Y Bisection of A276107.

%Y Cf. A064914, A000041, A002220, A002221, A002222, A213074, A006827, A046663.

%Y The strict version is A237258, ranked by A357854.

%Y Ranked by A357976 = positions of nonzero terms in A357879.

%Y A122768 counts distinct submultisets of partitions.

%Y A304792 counts subset-sums of partitions, positive A276024, strict A284640.

%Y Cf. A108917, A235130, A237194, A300061.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_

%E Better description from _Vladeta Jovovic_, Mar 06 2000

%E More terms from _Christian G. Bower_, Oct 12 2001

%E Edited by _N. J. A. Sloane_, Jun 03 2012

%E More terms from _Alois P. Heinz_, Jul 10 2012