Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 IntegerCompositions

Source Notebook

Generate all compositions of an integer into the specified number of parts

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["IntegerCompositions"][n,k]

gives a list of all compositions of integer n into k parts in canonical order.

Details and Options

A composition of n in ResourceFunction["IntegerCompositions"] is taken to be a particular arrangement of non-negative integers whose sum is n.

Examples

Basic Examples (1) 

Get every composition of 5 into three parts:

In[1]:=
ResourceFunction["IntegerCompositions"][5, 3]
Out[1]=

Properties and Relations (6) 

The number of compositions of n into k parts is Binomial[n+k-1,n]:

In[2]:=
n = 7; k = 3;
In[3]:=
ResourceFunction["IntegerCompositions"][n, k]
Out[3]=
In[4]:=
Length[%]
Out[4]=
In[5]:=
Binomial[n + k - 1, n]
Out[5]=

All compositions returned by IntegerCompositions are distinct:

In[6]:=
ResourceFunction["IntegerCompositions"][5, 2]
Out[6]=
In[7]:=
Length[%] === Length[Union[%]]
Out[7]=

Compositions are returned in Sort order:

In[8]:=
ResourceFunction["IntegerCompositions"][5, 3]
Out[8]=
In[9]:=
% === Sort[%]
Out[9]=

Integer compositions are related to integer partitions:

In[10]:=
IntegerPartitions[6, {3}]
Out[10]=

In contrast to compositions, partitions do not include 0 and are in non-increasing order:

In[11]:=
DeleteDuplicates[ ReverseSort /@ DeleteCases[ ResourceFunction["IntegerCompositions"][6, 3], {___, 0, ___}]]
Out[11]=

If you allow partitions to include 0, then all permutations thereof give the possible compositions:

In[12]:=
res = IntegerPartitions[6, {3}, Range[0, 6]]
Out[12]=
In[13]:=
Flatten[Permutations /@ res, 1] // Sort
Out[13]=
In[14]:=
ResourceFunction["IntegerCompositions"][6, 3]
Out[14]=

While IntegerCompositions allows resulting compositions to include 0, the resource function StrictIntegerCompositions does not:

In[15]:=
comp = ResourceFunction["IntegerCompositions"][4, 3]
Out[15]=
In[16]:=
scomp = ResourceFunction["StrictIntegerCompositions"][4, 3]
Out[16]=
In[17]:=
Sort[Union[DeleteCases[#, 0] & /@ comp]] == Sort[scomp]
Out[17]=

Version History

  • 1.0.0 – 06 March 2020

Related Resources

License Information