MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

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/



  • Prev by Date: Re: Generalized functions and integral transforms
  • Next by Date: Re: RE: Why can't I cut and paste between Mathematica and other applications?
  • Previous by thread: Re: Help! How to calculate additive partitions?
  • Next by thread: Re: Re: Re: Help! How to calculate additive partitions?