Partition-related sequence

[David Wilson]

What I am looking for is a multiset of integers that can be partitioned into 
k equal-sum multisets for k = 1, 2, 3, ..., n.

a(1) = 1 with optimal multiset [1] having partitions [[1]]
a(2) = 2 with optimal multiset [1 1] which partitions into [[1 1]] and [[1] 
[1]]
a(3) = 4 with optimal multiset [1 1 2 2] with partitions [[1 1 2 2]],  [[1 
2][1 2]]  and  [[1 1] [2] [2]]
a(4) = 6 with optimal multiset [1 1 2 2 3 3] and partitions
    [[1 1 2 2 3 3]],  [[1 1 2 2] [3 3]],  [[1 3] [1 3] [2 2]]  and  [[1 2] 
[1 2] [3] [3]]

I don't think you can do better for n = 1..4.

a(5) <= 10 with candidate optimal multiset [3 3 4 4 5 5 6 6 12 12]. This 
multiset can be partitioned into 1, 2, 3, 4 or 5 equal-sum sets. I don't 
know if there is a better set, but I doubt a(5) = 7 is achievable.

----- Original Message ----- 
From: <franktaw at netscape.net>
To: <seqfan at ext.jussieu.fr>
Sent: Wednesday, January 16, 2008 8:16 PM
Subject: Re: Partition-related sequence


> There is also some ambiguity in the question you are asking: do you want
> to count the number of ways to subpartition, or the number of distinct
> sums for the parts?  I will assume for the moment that it is the former.
>
> Note next that [1,1,2,2] is not the partition with the smallest sum that
> achieves this bound; [1,1,1,1] (which I prefer to write [1^4]) also does:
>   [1^4]
>   [1,1] [1,1]
>   [1] [1] [1] [1]
> and in general, we can always use [1^m] to achieve tau(m) parts.  In
> particular, this shows that a(4) <= 6.
>
> This is not usually the best way to do it, however; the partition
> [1^4,2^4] can be partitioned into equal parts 7 ways:
>   [1^4,2^4]
>   [1^4,2] [2^3]
>   [1,1,2,2] [1,1,2,2]
>   [1^4] [2,2] [2,2]
>   [1,1,2] [1,1,2] [2,2]
>   [1,2] [1,2] [1,2] [1,2]
>   [1,1] [1,1] [2] [2] [2] [2]
> This shows that a(7) <= 8.  The smallest number with tau(n) >= 7 is 24.
>
> We can also show that a(5) <= 7, using the partition [1^3,2^3,3].
>
> So we have upper bounds:
> 1,2,4,6,7,8,8
> where the first 3 values are known to be correct.  If these values are all
> correct, the sequence is not in the OEIS.
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: David W. Wilson <wilson.d at anseri.com>
>
> The partition (1, 1, 2, 2) can be split into either 1, 2, or
> 3 subpartitions having equal sum, to wit:
>
>     (1, 1, 2, 2)
>     (1, 2), (1, 2)
>     (1, 1), (2), (2)
>
> This is not possible for any smaller nonempty partition. If
> we define a(n) as the smallest number of elements in a partition that can 
> be
> split into 1 through n equal-sum subpartitions, this example shows a(3) = 
> 4.
>
> Can we find a few small a(n)? Is the sequence already in the
> OEIS?
>
>
>
>
>
>
> ________________________________________________________________________
> More new features than ever.  Check out the new AIM(R) Mail ! - 
> http://webmail.aim.com
>
>
> -- 
> No virus found in this incoming message.
> Checked by AVG Free Edition. Version: 7.5.516 / Virus Database: 
> 269.19.5/1228 - Release Date: 1/16/2008 9:01 AM
>