# compositions -- list the compositions of an integer

## Synopsis

• 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
• 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.