Re: Help! How to calculate additive partitions?
- To: mathgroup at smc.vnet.net
- Subject: [mg34436] Re: [mg34432] Help! How to calculate additive partitions?
- From: Andrzej Kozlowski <andrzej at platon.c.u-tokyo.ac.jp>
- Date: Mon, 20 May 2002 04:21:27 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Usually these things are called compositions, in the case of we
partitions do not distinguish order. The functions Compositions and
NumberOfCompositions are part of the Combinatorica package. However the
function Compositions[n,k] counts the number of compositions of n into k
parts where 0 is allowed to be one of the summands:
In[1]:=
<<DiscreteMath`Combinatorica`
In[2]:=
Compositions[4,4]
Out[2]=
{{0,0,0,4},{0,0,1,3},{0,0,2,2},{0,0,3,1},{0,0,4,0},{0,1,0,3},{0,1,1,2},
{0,1,2,
1},{0,1,3,0},{0,2,0,2},{0,2,1,1},{0,2,2,0},{0,3,0,1},{0,3,1,0},{0,4,0,
0},{1,0,0,3},{1,0,1,2},{1,0,2,1},{1,0,3,0},{1,1,0,2},{1,1,1,1},{1,1,2,
0},{1,2,0,1},{1,2,1,0},{1,3,0,0},{2,0,0,2},{2,0,1,1},{2,0,2,0},{2,1,0,
1},{2,1,1,0},{2,2,0,0},{3,0,0,1},{3,0,1,0},{3,1,0,0},{4,0,0,0}}
You can delete the 0's and take Union to leave you only with
"partitions" in your sense:
In[3]:=
Union[DeleteCases[Compositions[4,4],0,{2}]]
Out[3]=
{{4},{1,3},{2,2},{3,1},{1,1,2},{1,2,1},{2,1,1},{1,1,1,1}}
You cna use the Length function to calculate their number:
In[4]:=
Length[%]
Out[4]=
8
This approach is however very inefficient and will not get you far. If
you must deal with really large numbers you will have to use a different
method, most likely based on backtracking. I and others (particularly
Fred Simons) have already solved some very large problems of this kind
using this method. You can search the archive of this list for
"generalized partitions" and "backtracking".
On Sunday, May 19, 2002, at 05:15 PM, Thomas Brodhead wrote:
> Help!
>
> 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?
>
> Many thanks,
> --Tom
> ---------------------------------------------------------
> Tom Brodhead
> http://home.att.net/~tom.brodhead/
> ---------------------------------------------------------
>
>
>
>
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/