compositions -- list the compositions of an integer

Usage:

compositions(k, n)
Inputs:
- k, an integer, a nonnegative integer, the number of parts in each composition
- n, an integer, a nonnegative integer, the sum of each composition (if omitted, assumed to be also $k$)
Outputs:
- a list, of all ordered lists of k nonnegative integers that sum to n

Description

i1 : compositions(4, 2)

o1 = {{2, 0, 0, 0}, {1, 1, 0, 0}, {0, 2, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0},
     ------------------------------------------------------------------------
     {0, 0, 2, 0}, {1, 0, 0, 1}, {0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 2}}

o1 : List

i2 : compositions(2, 4)

o2 = {{4, 0}, {3, 1}, {2, 2}, {1, 3}, {0, 4}}

o2 : List

To find all unordered compositions, we can use sort or rsort to put each composition into a standard form, then use the function unique to remove duplicates.

i3 : unique apply(compositions(4, 10), comp -> rsort comp)

o3 = {{10, 0, 0, 0}, {9, 1, 0, 0}, {8, 2, 0, 0}, {7, 3, 0, 0}, {6, 4, 0, 0},
     ------------------------------------------------------------------------
     {5, 5, 0, 0}, {8, 1, 1, 0}, {7, 2, 1, 0}, {6, 3, 1, 0}, {5, 4, 1, 0},
     ------------------------------------------------------------------------
     {6, 2, 2, 0}, {5, 3, 2, 0}, {4, 4, 2, 0}, {4, 3, 3, 0}, {7, 1, 1, 1},
     ------------------------------------------------------------------------
     {6, 2, 1, 1}, {5, 3, 1, 1}, {4, 4, 1, 1}, {5, 2, 2, 1}, {4, 3, 2, 1},
     ------------------------------------------------------------------------
     {3, 3, 3, 1}, {4, 2, 2, 2}, {3, 3, 2, 2}}

o3 : List

In the next example, we use select to find all the compositions of 18 into 5 parts, with each part greater than or equal to 3.

i4 : select(compositions(5, 18), comp -> all(comp, c -> c>=3))

o4 = {{6, 3, 3, 3, 3}, {5, 4, 3, 3, 3}, {4, 5, 3, 3, 3}, {3, 6, 3, 3, 3}, {5,
     ------------------------------------------------------------------------
     3, 4, 3, 3}, {4, 4, 4, 3, 3}, {3, 5, 4, 3, 3}, {4, 3, 5, 3, 3}, {3, 4,
     ------------------------------------------------------------------------
     5, 3, 3}, {3, 3, 6, 3, 3}, {5, 3, 3, 4, 3}, {4, 4, 3, 4, 3}, {3, 5, 3,
     ------------------------------------------------------------------------
     4, 3}, {4, 3, 4, 4, 3}, {3, 4, 4, 4, 3}, {3, 3, 5, 4, 3}, {4, 3, 3, 5,
     ------------------------------------------------------------------------
     3}, {3, 4, 3, 5, 3}, {3, 3, 4, 5, 3}, {3, 3, 3, 6, 3}, {5, 3, 3, 3, 4},
     ------------------------------------------------------------------------
     {4, 4, 3, 3, 4}, {3, 5, 3, 3, 4}, {4, 3, 4, 3, 4}, {3, 4, 4, 3, 4}, {3,
     ------------------------------------------------------------------------
     3, 5, 3, 4}, {4, 3, 3, 4, 4}, {3, 4, 3, 4, 4}, {3, 3, 4, 4, 4}, {3, 3,
     ------------------------------------------------------------------------
     3, 5, 4}, {4, 3, 3, 3, 5}, {3, 4, 3, 3, 5}, {3, 3, 4, 3, 5}, {3, 3, 3,
     ------------------------------------------------------------------------
     4, 5}, {3, 3, 3, 3, 6}}

o4 : List

For partitions of n into unordered, strictly positive parts, use partitions instead.

If a negative integer is given for n, an empty list is returned. If a negative integer is given for k, it will cause an error.

Ways to use compositions:

compositions(ZZ)
compositions(ZZ,ZZ)

For the programmer

The object compositions is a method function.

The source of this document is in Macaulay2Doc/functions/compositions-doc.m2:47:0.

compositions -- list the compositions of an integer

Description

See also

Ways to use compositions:

For the programmer