Re: Help! How to calculate additive partitions?
- To: mathgroup at smc.vnet.net
- Subject: [mg34437] Re: [mg34432] Help! How to calculate additive partitions?
- From: BobHanlon at aol.com
- Date: Mon, 20 May 2002 04:21:28 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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