A387388 a(n) is the maximum number of ways in which any strict partition of 2n can be partitioned into two disjoint subsets of equal sum.

0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 4, 4, 4, 4, 7, 6, 6, 6, 6, 11, 11, 10, 10, 10, 19, 18, 18, 18, 17, 35, 33, 32, 32, 31, 31, 62, 60, 58, 57, 57, 55, 56, 108, 105, 103, 101, 100, 100, 99, 195, 191, 187, 184, 182, 181, 180, 361, 352, 344, 340, 336, 333

Offset: 1

Author

Jesús Bellver Arnau, Aug 28 2025

Keywords

• nonn
• new

Comments

Finding the number of ways in which a set can be partitioned into two disjoint subsets with equal sum is often referred to as the "partition search problem".

The sequence is defined for partitions of 2n because for odd numbers there are no solutions.

Examples

			a(2) = 0, because strict partitions of 4 are {4} and {3,1}. None of these partitions can be partitioned into two disjoint subsets of equal sum.
a(3) = 1, because strict partitions of 6 are {6}, {5,1}, {4,2} and {3,2,1}. There is one way to partition {3,2,1} into two disjoint subsets of equal sum: {3}={2,1}. For the other partitions, this cannot be done.
a(11) = 2, because among the 89 strict partitions of 22 there is {7, 5, 4, 3, 2, 1}. There are two ways to partition {7, 5, 4, 3, 2, 1} into two disjoint subsets of equal sum: {7,4}={5,3,2,1} and {7,3,1}={5,4,2}. And this cannot be done in three ways for any strict partition of 22.
		

Links

• Jesús Bellver Arnau, Table of n, a(n) for n = 1..80
• Wikipedia, Partition problem.

Crossrefs

Cf. A000009, A387388, A083206, A237258, A321452, A305551, A371791.

Programs

Python

def partitions_distinct(n):
    def _build(remaining, max_next):
        if remaining == 0:
            return [[]]
        res = []
        for k in range(min(remaining, max_next), 0, -1):
            for tail in _build(remaining - k, k - 1):
                res.append([k] + tail)
        return res
    return _build(n, n//2) # The biggest number in the subset can't be bigger than n/2
def count_half_subsets(partition, n):
    if n % 2:
        return 0
    half = n // 2
    dp = [0] * (half + 1)
    dp[0] = 1
    for x in partition:
        for s in range(half, x - 1, -1):
            dp[s] += dp[s - x]
    return int(dp[half]/2) #-> to not count {X}={Y} and {Y}={X} as two different solutions
#---- Generate Sequence -----
sequence = []
max_n=25  #number of terms
for N in range(1, max_n):
    parts = partitions_distinct(2*N)
    max_sols = 0
    for p in parts:
        subsets = count_half_subsets(p, 2*N)
        if subsets > max_sols:
            max_sols = subsets
    sequence.append(max_sols)