Partition-related sequence
zak seidov
zakseidov at yahoo.com
Fri Jan 18 04:17:57 CET 2008
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
More information about the SeqFan
mailing list