Partition-related sequence

[zak seidov]

Take the first Frank's set: 
F1={2,2,2,3,3,3,4,5,6,10,10,10}.

Then  numbers of ways of splitting F1 into n groups
with equal sum 60/n are:
a(1..6)=1,7,8,2,1,2.

Splittings in 1 group:
F1.
Splittings in 2 groups:
{{10,10,10},{2,2,2,3,3,3,4,5,6}},
{{4,6,10,10},{2,2,2,3,3,3,5,10}},
{{2,2,6,10,10},{2,3,3,3,4,5,10}},
{{2,3,5,10,10},{2,2,3,3,4,6,10}},
{{3,3,4,10,10},{2,2,2,3,5,6,10}},
{{2,2,2,4,10,10},{3,3,3,5,6,10}},
{{2,2,3,3,10,10},{2,3,4,5,6,10}}}.
Splittings in 3 groups:
{{10,10},{4,6,10},{2,2,2,3,3,3,5}},
{{10,10},{2,2,6,10},{2,3,3,3,4,5}},
{{10,10},{2,3,5,10},{2,2,3,3,4,6}},
{{10,10},{3,3,4,10},{2,2,2,3,5,6}},
{{10,10},{2,2,2,4,10},{3,3,3,5,6}},
{{10,10},{2,2,3,3,10},{2,3,4,5,6}},
{{4,6,10},{2,3,5,10},{2,2,3,3,10}},
{{2,2,6,10},{2,3,5,10},{3,3,4,10}}}.
Splittings in 4 groups:
{{5,10},{2,3,10},{2,3,10},{2,3,4,6}},
{{2,3,10},{2,3,10},{2,3,10},{4,5,6}}}.
Splitting in 5 groups:
{{{2,10},{2,10},{2,10},{3,3,6},{3,4,5}}.
Splittings in 6 groups:
{{2,2,6},{2,3,5},{3,3,4},{10},{10},{10}},
{{2,3,5},{2,2,3,3},{4,6},{10},{10},{10}}.

All modulo my errs, 
zak

--- franktaw at netscape.net wrote:

> From David Wilson <davidwwilson at comcast.net>:
> >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.
> 
> OK, I see now what you are trying to do.  Actually,
> I think my
> question is at least equally interesting, but yours
> is interesting.
> 
> For your problem, I get a(6) <= 12, using any of
> [2,2,2,3,3,3,4,5,6,10,10,10],
> [2,2,2,3,3,4,4,5,5,10,10,10],
> [1,1,2,2,2,2,5,5,10,10,10,10], or
> [2,2,3,3,3,3,5,5,7,7,10,10].
> 
> Even assuming these values are correct for n = 1..6
> is not
> enough to determine the sequence, but A002088 is an
> intriguing possibility.
> 
> There is a systematic way to get a solution for
> a(n+1) from
> a solution for a(n), adding n new values.  Multiply
> each term
> by the appropriate factor to get a sum divisible by
> the lcm
> of the sum used for a(n) (is A003418 always
> achievable?)
> and n+1, look at the groups summing to the total
> divided
> by n.  Split one of the values in each group so that
> the total
> divided by n+1 is achievable.  This is then a
> solution.
> 
> For example, n = 4, the partition is [1,1,2,2,3,3]. 
> Multiplying
> by 5 to get a sum of 60, we have parts summing to 15
> of
> [5,10] [5,10] [15] [15].  Splitting these, we get
> two parts
> of [12,3], and two that are either [10,3,2] or
> [7,5,3].
> 
> This shows that a(n+1) <= a(n) + n.
> 
> Actually, when n+1 is composite, we can do better
> than this.
> Let k be any factor of n+1.  Divide the solution for
> n into k
> parts, and subdivide number each part so that it be
> divided
> into (n+1)/k parts; this requires splitting at most
> (n+1)/k - 1
> parts.  This gives us a solution using a(n) +
> k*((n+1)/k - 1)
> = a(n) + n + 1 - k parts.  This is minimized when
> k = (n + 1) / lpf(n + 1), where lpf is the least
> prime factor
> function.  So we get, substituting n -> n-1,
> 
> a(n) <= a(n-1) + n - n/lpf(n).
> 
> Note that this is not always optimal; it gives a(6)
> <= 13, but
> we can achieve a(6) <= 12.  (Or if a(5) < 10, then
> a(5) is
> an exception instead.)  This difference can be
> explained by
> noting that when we split (at least one of the)
> solutions for
> a(5) into 2 parts, one of the parts is [10,10],
> which needs
> no subdivision to split into halves.
> 
> I will conjecture that A002088 is in fact the
> solution to this
> problem.
> 
> A final note: this problem is equivalent to asking
> how many
> positive fractions are required so that they can
> divided into
> k groups, each summing to 1/k, for every k from 1 to
> n.
> 
> Franklin T. Adams-Watters
> 
> 
>
________________________________________________________________________
> More new features than ever.  Check out the new
> AIM(R) Mail ! - 
> http://webmail.aim.com
> 



      ____________________________________________________________________________________
Be a better friend, newshound, and 
know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ