[Previous] [Next] [Contents]

## `combinat::compositions` -- compositions of an integer

#### Introduction

The library `combinat::compositions` provides functions for counting, generating, and manipulating compositions.

#### Details

- A composition `c` of a nonnegative integer `n` is a list of positive integers with total sum `n`.

- All functions for counting and generating accept the following optional constraints on the compositions: MinLength, MaxLength, Length, MinPart, MaxPart, Inner, Outer, MinSlope, and MaxSlope. Cf. examples 3, 4, 5, 6, and 7.

- Generally, compositions of n are used to encode subset of {1,..., n-1} through the bijection: I=(i_1, i_2, ..., i_k) Des(I)= {i_1, i_1+i_2, ..., i_1+i_2+...+i_k} The set Des(I) is called the descents set of the composition I. The converse bijection is given by {c_1 < c_2 < ...< c_l}⊂{1, ..., n-1} (c_1, c_2-c_1, ..., c_l-c_l-1, n-c_l) In MuPAD the descents set can be stored as a set or a list.

- The inclusion of descents set gives rise to a partial order on compositions: I ≤J if and only if Des(I) ⊂Des(J) . This order is called the refinement order; the composition J is said to be finer than I. And I is said to be fatter than J.

#### Categories

`Cat::IntegerListsLexClass`

#### Related Domains

`combinat::partitions`, `combinat::words`

#### Entries

domtype

The MuPAD domain of compositions: `DOM_LIST`

#### Method isA: test if an object is a composition

- `isA(any type co <, nonnegative integer n <, constraints>>)`

- Returns whether `co` is a composition.
- If the optional argument `n` is present, returns whether `co` is a composition of `n`.
- If constraints are given, returns whether `co` is a composition satisfying `constraints`.

#### Method count: number of compositions

- `count(nonnegative integer n <, constraints>)`

- Returns the number of compositions of `n` satisfying `constraints`.

#### Method generator: generator for compositions

- `generator(nonnegative integer n <, constraints>)`

- Returns a generator for the compositions of `n` satisfying `constraints`.

#### Method list: list of the compositions

- `list(nonnegative integer n <, constraints>)`

- Returns the list of the compositions of `n` satisfying `constraints`.

#### Method first: first composition

- `first(nonnegative integer n <, constraints>)`

- Returns the first composition of `n` satisfying `constraints` or `FAIL` if there is none.

#### Method Next: next composition

- `Next(composition c <, constraints>)`

- Returns the composition following `c` satisfying `constraints` or `FAIL` if there is none.

#### Method descents: descents of a composition

- `descents(composition c)`

- Returns the list of descents of the composition `c`

#### Method descentsSet: descents of a composition

- `descentsSet(composition c)`

- Returns the set of descents of the composition `c`

#### Method fromDescents: composition of given descents

- `fromDescents(descent set s)`
- `fromDescents(descent list l)`

- Returns the composition `c` whose descents set is `s` or `l`

#### Method majorIndex: major index of a composition

- `majorIndex(composition c)`

- Returns the major index composition `c`, defined as the sum of the descents.

#### Method isFiner: compare two compositions for the refinement order

- `isFiner(composition c1, composition c2)`

- Returns whether the composition `c1` is finer than the composition `c2`.

#### Method finer: compositions finer than a composition

- `finer(composition c)`

- Returns the compositions finer than `c`. Note that `compositons::finer` is a full combinatorial class that implement the standard methods `compositions::finer::count` and `compositions::finer::generators`.

#### Method fatter: compositions fatter than a composition

- `fatter(composition c)`

- Returns the compositions fatter than `c`. Note that `compositons::fatter` is a combinatorial class that implement the standard methods `compositions::fatter::count` and `compositions::fatter::generators`.

#### Example 1

This example shows how to test if an object is of type `combinat::compositions`:

    >> combinat::compositions::isA([3,4]);
       combinat::compositions::isA([3,4],7);
       combinat::compositions::isA([3,4],5);

                                       TRUE

                                       TRUE

                                       FALSE

The `combinat::compositions::isA` function admets the same constraints than other functions in the package.

    >> combinat::compositions::isA([4,2], 6, Inner=[2, 2], MinPart=2);
       combinat::compositions::isA([4,2], 6, Inner=[2, 2], MaxPart=4);

                                       TRUE

                                       TRUE

Please note that given constraints should be compatible:

    >> combinat::compositions::isA([4,1], 5, Inner=[2, 1], MinPart=2);

                                       TRUE

See further examples for other constraints.

#### Example 2

There are 8 compositions of 4:

    >> combinat::compositions::count(4)

                                         8

Here is the list:

    >> combinat::compositions::list(4)

          [[4], [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2],

             [1, 1, 1, 1]]

You can use the function `combinat::compositions::first` to get the ``first'' composition of a number:

    >> combinat::compositions::first(4)

                                        [4]

Using `combinat::compositions::Next`, you can calculate the ``next'' composition. This function takes as argument the composition relative to which you want the next one:

    >> combinat::compositions::Next([4])

                                      [3, 1]

`combinat::compositions::Next` returns `FAIL` when the input is the last composition:

    >> combinat::compositions::Next([1, 1, 1, 1])

                                       FAIL

When you want to run through the compositions of a number, you can generate them one by one to save memory:

    >> g := combinat::compositions::generator(3):
       g(); g(); g(); g(); g();

                                        [3]

                                      [2, 1]

                                      [1, 2]

                                     [1, 1, 1]

                                       FAIL

Typically, this would be used as follows:

    >> g := combinat::compositions::generator(3):
       while (p := g()) <> FAIL do print(p): end:

                                        [3]

                                      [2, 1]

                                      [1, 2]

                                     [1, 1, 1]

#### Example 3

The options Length, MinLength, and MaxLength can be used to set length constraints. This is the list of the compositions of 4 of length 2:

    >> combinat::compositions::list(4, Length=2)

                             [[3, 1], [2, 2], [1, 3]]

This is the list of the compositions of 4 of length at least 2:

    >> combinat::compositions::list(4, MinLength=2)

          [[3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2],

             [1, 1, 1, 1]]

This is the list of the compositions of 4 of length at most 2:

    >> combinat::compositions::list(4, MaxLength=2)

                           [[4], [3, 1], [2, 2], [1, 3]]

Setting both MinLength and MaxLength to the same value is equivalent to setting Length to this value. This is again the list of the compositions of 4 of length 2:

    >> combinat::compositions::list(4, MinLength=2, MaxLength=2)

                             [[3, 1], [2, 2], [1, 3]]

#### Example 4

The options MinPart and MaxPart can be used to set constraints on the sizes of all parts. Using MaxPart, you can select compositions having only small entries. This is the list of the compositions of 4 with all parts at most 2:

    >> combinat::compositions::list(4, MaxPart=2)

              [[2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]

MinPart is complementary to MaxPart and selects compositions having only large parts (it takes a non-negative value). This is the list of the compositions of 4 with all parts at least 2:

    >> combinat::compositions::list(4, MinPart=2)

                                   [[4], [2, 2]]

By default, the parts of a composition have to be positive. This can be changed using the option MinPart. In the following example, the options Length and MinPart are combined together to obtain the list of the compositions of 4 with 3 nonnegative parts:

    >> combinat::compositions::list(4, Length=3, MinPart=0)

          [[4, 0, 0], [3, 1, 0], [3, 0, 1], [2, 2, 0], [2, 1, 1],

             [2, 0, 2], [1, 3, 0], [1, 2, 1], [1, 1, 2], [1, 0, 3],

             [0, 4, 0], [0, 3, 1], [0, 2, 2], [0, 1, 3], [0, 0, 4]]

If the list you ask for is infinite, the program will not finish, as it is be the case for `combinat::compositions::list(4, MinPart=0);`

Two compositions are considered equivalent whenever they differ only by trailing zeroes. Whenever two equivalent compositions satisfy the constraints, only the shortest one is considered. Hence, this is the list of compositions of 4 with 2 or 3 nonnegative parts:

    >> combinat::compositions::list(4, MinLength=2, MaxLength=3, MinPart=0)

          [[4, 0], [3, 1], [3, 0, 1], [2, 2], [2, 1, 1], [2, 0, 2],

             [1, 3], [1, 2, 1], [1, 1, 2], [1, 0, 3], [0, 4], [0, 3, 1],

             [0, 2, 2], [0, 1, 3], [0, 0, 4]]

#### Example 5

The options Inner, and Outer can be used to set part-by-part containment constraints. This is the list of the compositions of 4 bounded above by `[3, 1, 2]`:

    >> combinat::compositions::list(4, Outer=[3, 1, 2])

                          [[3, 1], [2, 1, 1], [1, 1, 2]]

Outer sets MaxLength to the length of its argument. Moreover, the parts of Outer may be infinite to clear the constraint on specific parts. This is the list of compositions of 4 of length at most 3 such that the first and third parts are at most 1:

    >> combinat::compositions::list(4, Outer=[1, infinity, 1])

                                [[1, 3], [1, 2, 1]]

This is the list of compositions of 4 bounded below by `[1, 1, 1]`:

    >> combinat::compositions::list(4, Inner=[1, 1, 1])

                  [[2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]

#### Example 6

The options MinSlope and MaxSlope can be used to set constraints on the slope, that is on the difference `p[i+1]-p[i]` of two consecutive parts. This is the list of the increasing compositions of 4:

    >> combinat::compositions::list(4, MinSlope=0)

                  [[4], [2, 2], [1, 3], [1, 1, 2], [1, 1, 1, 1]]

This is the list of compositions of 4 such that two consecutive parts differ by at most one unit:

    >> combinat::compositions::list(4, MinSlope=-1, MaxSlope=1)

           [[4], [2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]

#### Example 7

The constraints can be combined together in all reasonable ways. This is the list of compositions of 5 of length between 2 and 4 such that the difference between two consecutive parts is between -2 and 1:

    >> combinat::compositions::list(5,
                                    MaxSlope=1, MinSlope=-2,
                                    MinLength=2, MaxLength=4)

          [[3, 2], [3, 1, 1], [2, 3], [2, 2, 1], [2, 1, 2],

             [2, 1, 1, 1], [1, 2, 2], [1, 2, 1, 1], [1, 1, 2, 1],

             [1, 1, 1, 2]]

Idem with an Outer constraint:

    >> combinat::compositions::list(5,
                                    MaxSlope=1, MinSlope=-2,
                                    MinLength=2, MaxLength=4,
                                    Outer=[2,5,2])

                     [[2, 3], [2, 2, 1], [2, 1, 2], [1, 2, 2]]

However, providing incoherent constraints may yield strange results. It is up to the user to ensure that the Inner and Outer compositions themselves satisfy the parts and slope constraints:

    >> combinat::compositions::list(5, Inner=[2, 1], MinPart=2)

                        [[4, 1], [3, 2], [2, 3], [2, 1, 2]]

#### Example 8

One can check that those two compositions are not comparable for the refinement order:

    >> combinat::compositions::isFiner([4,1,2],[3,1,3]);
       combinat::compositions::isFiner([3,1,3],[4,1,2]);

                                       FALSE

                                       FALSE

To get the list of compositions finer than `[4,1,2]`, you can use:

    >> combinat::compositions::finer([4,1,2]);

          [[4, 1, 2], [4, 1, 1, 1], [3, 1, 1, 2], [3, 1, 1, 1, 1],

             [2, 2, 1, 2], [2, 2, 1, 1, 1], [2, 1, 1, 1, 2],

             [2, 1, 1, 1, 1, 1], [1, 3, 1, 2], [1, 3, 1, 1, 1],

             [1, 2, 1, 1, 2], [1, 2, 1, 1, 1, 1], [1, 1, 2, 1, 2],

             [1, 1, 2, 1, 1, 1], [1, 1, 1, 1, 1, 2],

             [1, 1, 1, 1, 1, 1, 1]]

To get the list of compositions fatter than `[4,1,2]`, you can use:

    >> combinat::compositions::fatter([4,1,2]);

                         [[7], [5, 2], [4, 3], [4, 1, 2]]

If you only want their number, you can ask:

    >> combinat::compositions::fatter::count([4,1,2]);

                                         4

#### Background

- Compositions are naturally ordered lexicographically. The functions for counting and generating are directly inherited from `Cat::IntegerListsLexClass` with, by default, `MinPart=1`. The complexity of the generation algorithm is constant time amortized for each composition generated.

- Except for the trivial cases, counting is done by brute force generation.

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package