A276107 Number of partitions of n which can themselves be subdivided into two partitions whose sums differ by 1 at most.

1, 1, 1, 2, 3, 5, 6, 11, 14, 22, 25, 43, 53, 79, 89, 140, 167, 243, 278, 409, 480, 666, 760, 1082, 1273, 1708, 1948, 2649, 3089, 4073, 4682, 6180, 7177, 9213, 10565, 13660, 15869, 19987, 22911, 29012, 33601, 41762, 47942, 59571, 68756, 84240, 96570, 118641

Offset: 0

Author

David S. Newman, Aug 18 2016

Keywords

• nonn

Comments

Number of partitions whose summands can be divided into two sets whose sums are equal, or whose sums differ by one.

Examples

			For example: the partition of 6 into 2+2+2 is not counted because no subset of {2,2,2} has the sum 3. The partition of 6 into 3+2+1 is counted because {3,2,1} can be divided into two subsets {3} and {2,1} each of which has sum 3. The partition of 7 into 4+2+1 is counted because {4,2,1} can be broken up into sets {4} and {2,1} the sum of whose elements differ by one.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..115 (first 77 terms from Chai Wah Wu)

Crossrefs

Cf. A000041, A002219, A046663.

Programs

Maple

N:= 50: # to get a(0) .. a(N)
Pm1:= combinat:-partition(0);
for m from 0 to N/2 do
  Pm:= Pm1;
  A[2*m]:= nops({seq(seq(sort([op(Pm[i]),op(Pm[j])]),j=1..i),i=1..nops(Pm))});
  if 2*m+1 > N then break fi;
  Pm1:= combinat:-partition(m+1);
  A[2*m+1]:= nops({seq(seq(sort([op(Pm[i]),op(Pm1[j])]),j=1..nops(Pm1)),i=1..nops(Pm))});
od:
seq(A[i],i=  0..N); # Robert Israel, Aug 18 2016

Python

from collections import Counter
from sympy.utilities.iterables import partitions
def A276107(n): return len({tuple(sorted((p+q).items())) for p in (Counter(p) for p in partitions(n>>1)) for q in (Counter(q) for q in partitions(n+1>>1))}) # Chai Wah Wu, Sep 20 2023

Formula

a(n) = A000041(n) - A046663(n,floor(n/2)). - Max Alekseyev, Oct 17 2022

Extensions

a(11)-a(47) from Alois P. Heinz, Aug 18 2016