A002219 - OEIS

A002219

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)

1, 3, 6, 14, 25, 53, 89, 167, 278, 480, 760, 1273, 1948, 3089, 4682, 7177, 10565, 15869, 22911, 33601, 47942, 68756, 96570, 136883, 189674, 264297, 362995, 499617, 678245, 924522, 1243098, 1676339, 2237625, 2988351, 3957525, 5247500, 6895946, 9070144, 11850304

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

OFFSET

1,2

REFERENCES

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

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

LINKS

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..140 (terms 1..89 from Alois P. Heinz)

N. Metropolis and P. R. Stein, An elementary solution to a problem in restricted partitions, J. Combin. Theory, 9 (1970), 365-376.

Vladimir A. Shlyk, Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number, arXiv:1805.07989 [math.CO], 2018.

FORMULA

See A213074 for Metropolis and Stein's formulas.

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

a(n) = A276107(2*n). - Max Alekseyev, Oct 17 2022

EXAMPLE

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

From Gus Wiseman, Oct 27 2022: (Start)

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

(11) (22) (33) (44)

(211) (321) (422)

(1111) (2211) (431)

(3111) (2222)

(21111) (3221)

(111111) (3311)

(4211)

(22211)

(32111)

(41111)

(221111)

(311111)

(2111111)

(11111111)

(End)

MAPLE

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

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

end:

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

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

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

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

end:

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

seq(a(n), n=1..25); # Alois P. Heinz, Jul 10 2012

MATHEMATICA

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

primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];

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

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

PROG

(Python)

from itertools import combinations_with_replacement

from sympy.utilities.iterables import partitions

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

CROSSREFS

Column m=2 of A213086.

Bisection of A276107.

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

The strict version is A237258, ranked by A357854.

Ranked by A357976 = positions of nonzero terms in A357879.

A122768 counts distinct submultisets of partitions.

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

Cf. A108917, A235130, A237194, A300061.

Sequence in context: A285460 A236429 A316245 * A006906 A324703 A120940

Adjacent sequences: A002216 A002217 A002218 * A002220 A002221 A002222

KEYWORD