RE: Re: Re: Re: Help! How to calculate additive partitions?
- To: mathgroup at smc.vnet.net
- Subject: [mg34474] RE: [mg34446] Re: [mg34440] Re: Re: [mg34432] Help! How to calculate additive partitions?
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Thu, 23 May 2002 03:32:14 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
> -----Original Message----- > From: Andrzej Kozlowski [mailto:andrzej at tuins.ac.jp] To: mathgroup at smc.vnet.net > Sent: Tuesday, May 21, 2002 9:36 AM > Subject: [mg34474] [mg34446] Re: [mg34440] Re: Re: [mg34432] Help! How to > calculate additive partitions? > > > > 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/ > > Andrzej, Fred, Rob and Bob, just for fun, here a direct implementation of the deduction above In[18]:= n = 5; In[19]:= Map[Length, Split[#, 1 =!= #2 &] & /@ Table[IntegerDigits[k, 2, n], {k, 2^(n - 1), 2^n - 1}], {2}] Out[19]= {{5}, {4, 1}, {3, 2}, {3, 1, 1}, {2, 3}, {2, 2, 1}, {2, 1, 2}, {2, 1, 1, 1}, {1, 4}, {1, 3, 1}, {1, 2, 2}, {1, 2, 1, 1}, {1, 1, 3}, {1, 1, 2, 1}, {1, 1, 1, 2}, {1, 1, 1, 1, 1}} The ones in the binary representation of the integer k constitute the markers. In performance though, this cannot cope with Bob's solution. -- Hartmut