Partition-related sequence
David Wilson
davidwwilson at comcast.net
Thu Jan 17 04:08:56 CET 2008
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
>
More information about the SeqFan
mailing list