Re: Re: Re: Help! How to calculate additive partitions?
- To: mathgroup at smc.vnet.net
- Subject: [mg34446] Re: [mg34440] Re: Re: [mg34432] Help! How to calculate additive partitions?
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Tue, 21 May 2002 03:36:23 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Bob's gave certainly the best way find the number of "partitions" and to
create a list of all of them. However since he did not give a proof that
there are exactly 2^(n-1) of them I thought it might be of some interest
to provide one.
You can see that this must be the right answer as follows. Write n as a
sum of 1's, e.g.
5 = 1 + 1 + 1 + 1 + 1
To create a "partition" we simply insert a separators (e.g. |) into this
expression and sum up everything between the separators (there is always
a separators in the first and last place). Thus the expression:
|1+1|+1+1|+1|
corresponds to the partition 2+2+1 etc. So now we only need to find the
number of ways to insert separators. Since there are (n-1) positions for
a separator and two choices (a separator may be inserted or may not be)
the answer is indeed 2^(n-1).
Andrzej
On Monday, May 20, 2002, at 05:21 PM, BobHanlon at aol.com wrote:
>
> A much faster way came to mind:
>
> Needs["DiscreteMath`Combinatorica`"];
>
> myPartitions[n_Integer?Positive] :=
>
> Flatten[Permutations /@ Partitions[n],1]
>
> n=5;
> myPartitions1[n]
>
> {{5}, {1, 4}, {2, 3}, {3, 2}, {4, 1}, {1, 1, 3}, {1, 2, 2},
>
> {1, 3, 1}, {2, 1, 2}, {2, 2, 1}, {3, 1, 1}, {1, 1, 1, 2},
>
> {1, 1, 2, 1}, {1, 2, 1, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}}
>
> Length[%]==2^(n-1)
>
> True
>
>
> In a message dated 5/19/02 12:01:55 PM, writes:
>
>> In a message dated 5/19/02 5:08:45 AM, Tom.Brodhead at worldnet.att.net
>> writes:
>>
>>> I need to find a formula or method that will allow me to calculate the
>>> additive partitions of a given number.
>>>
>>> E.g., 3 can be expressed as
>>>
>>> 1+1+1
>>> 2+1
>>> 1+2
>>> 3
>>>
>>> IMPORTANT: Even though 2+1 and 1+2 employ the same values, the order
>>> is
>>> important and thus the procedure or formula that I need would need to
>>> produce both of those results.
>>>
>>> Likewise, 4 would break down this way:
>>> 1+1+1+1
>>> 2+1+1
>>> 1+2+1
>>> 1+1+2
>>> 2+2
>>> 3+1
>>> 1+3
>>> 4
>>>
>>> I need to calculate both the number of results that I should get, and
>> the
>>> results themselves.
>>>
>>> How can this be done?
>>>
>>
>> Needs["DiscreteMath`Combinatorica`"];
>>
>>
>> A brute force approach which gets quite slow for large n:
>>
>>
>> myPartitions[n_Integer?Positive] :=
>>
>> Union[Flatten[Table[Compositions[n,k],{k,n}],1] //.
>>
>> {x___,0,y___}:> {x,y}];
>>
>>
>> myPartitions[3]
>>
>>
>> {{3}, {1, 2}, {2, 1}, {1, 1, 1}}
>>
>>
>> myPartitions[4]
>>
>>
>> {{4}, {1, 3}, {2, 2}, {3, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {1, 1,
>> 1,
>> 1}}
>>
>>
>> The number of results for myPartitions[n] is just 2^(n-1)
>>
>>
>> Table[{n,l=Length[myPartitions[n]], l==2^(n-1)}, {n,7}]
>>
>>
>> {{1, 1, True}, {2, 2, True}, {3, 4, True}, {4, 8, True},
>> {5, 16, True}, {6, 32, True}, {7, 64, True}}
>>
>>
>> numberOfMyPartitions[n_Integer?Positive] := 2^(n-1);
>>
>
> Bob Hanlon
> Chantilly, VA USA
>
>
>
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/