Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Help! How to calculate additive partitions?

• To: mathgroup at smc.vnet.net
• Subject: [mg34441] Re: [mg34432] Help! How to calculate additive partitions?
• From: "Fred Simons" <f.h.simons at tue.nl>
• Date: Tue, 21 May 2002 03:36:17 -0400 (EDT)
• References: <200205190815.EAA24177@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Tom,

Let n be a positive integer and let f[n] be the list of all additive
partitions of n. The partitions starting with 1 have the additive partitions
of n-1 as rest, those starting with 2 are followed by the additive
partitions of n-2 and so on. From this observation we conclude that the
length of f[n] equals 2^(n-1). So to construct all partitions is only
feasible for small values of n. We then can use the following recursive
implementation of the idea above:

f[0]={{}};
f[n_Integer] := Flatten[Table[{k, ##}& @@@ f[n-k], {k, 1, n}], 1]

In[117]:= f[4]

Out[117]=
{{1,1,1,1},{1,1,2},{1,2,1},{1,3},{2,1,1},{2,2},{3,1},{4}}

Indeed we have 2^(4-1) partitions.

Fred Simons
Eindhoven University of Technology

• References:
  • Help! How to calculate additive partitions?
    • From: "Thomas Brodhead" <Tom.Brodhead@worldnet.att.net>