Re: Help! How to calculate additive partitions?
- To: mathgroup at smc.vnet.net
- Subject: [mg34443] Re: [mg34432] Help! How to calculate additive partitions?
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Tue, 21 May 2002 03:36:19 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
On Sun, 19 May 2002, 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/ > --------------------------------------------------------- The following method is slower than the ones already proposed using Partitions and Permutations, but it does illustrate an interesting bijection between ordered partitions of n and subsets of {1, ..., n - 1}. The idea is basically the old "dots and dividers" interpretation. Place n dots in a row and place dividers in the n - 1 spaces between dots. The dividers delimit the parts of the partition. For example, the ordered partition 1 + 3 + 2 corresponds to the following arrangement of dots and dividers . | . . . | . . Since each of the n - 1 spaces either has a divider or doesn't, we have 2 ^ (n - 1) such arrangements, hence 2 ^ (n - 1) ordered partitions of n. The code below generates the ordered partitions by mapping each subset of {1, ..., n - 1} (the dividers) to its corresponding ordered partition. Needs["DiscreteMath`Combinatorica`"] diff[lis_List] := Rest[lis - RotateRight[lis]] subsetToOrderedPartition[lis_List, n_Integer] := diff[Join[{0}, lis, {n}]] orderedPartitions[n_Integer] := (subsetToOrderedPartition[#, n] & ) /@ Subsets[Range[n - 1]] Calling orderedPartitions[4] then yields {{4}, {1, 3}, {1, 1, 2}, {2, 2}, {2, 1, 1}, {1, 1, 1, 1}, {1, 2, 1}, {3, 1}} Rob Pratt Department of Operations Research The University of North Carolina at Chapel Hill rpratt at email.unc.edu http://www.unc.edu/~rpratt/