OFFSET
1,11
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.
LINKS
Jesús Bellver Arnau, Table of n, a(n) for n = 1..80
Wikipedia, Partition problem.
EXAMPLE
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.
PROG
(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)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jesús Bellver Arnau, Aug 28 2025
STATUS
approved