[Previous] [Next] [Contents]

## `combinat::integerVectors` -- integer vectors

#### Introduction

The library `combinat::integerVectors` provides functions for counting, generating, and manipulating integer vectors.

#### Details

- An integer vector `v` of sum `n` with `k` parts is a list of `k` nonnegative integers which sum up to `n`.

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

#### Categories

`Cat::IntegerListsLexClass`

#### Related Domains

`combinat::words`

#### Entries

domtype

The MuPAD domain used to represent integer vectors: `DOM_LIST`

#### Method count: number of integer vectors

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

- Returns the number of integer vectors of sum `n` with `k` parts satisfying `constraints`.

#### Method generator: generator for integer vectors

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

- Returns a generator for the integer vectors of sum `n` with `k` parts satisfying `constraints`.

#### Method list: list of the integer vectors

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

- Returns the list of the integer vectors of sum `n` with `k` parts satisfying `constraints`.

#### Method first: first integer vector

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

- Returns the first integer vector of sum `n` with `k` parts satisfying `constraints` or `FAIL` if there is none.

#### Method Next: next integer vector

- `Next(integer vector v <, constraints>)`

- Returns the integer vector following `v` satisfying `constraints` or `FAIL` if there is none.

#### Example 1

There are 15 integer vectors of sum 4 with 3 parts:

    >> combinat::integerVectors::count(4, 3)

                                        15

Here is the list:

    >> combinat::integerVectors::list(4, 3)

          [[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]]

You can use the function `combinat::integerVectors::first` to get the ``first'' integer vector of a given sum:

    >> combinat::integerVectors::first(4, 3)

                                     [4, 0, 0]

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

    >> combinat::integerVectors::Next([4, 0, 0])

                                     [3, 1, 0]

`combinat::integerVectors::Next` returns `FAIL` when the last integer vector is given in the input:

    >> combinat::integerVectors::Next([0, 0, 4])

                                       FAIL

If you want to run through the integer vectors of a given sum, you can generate them one by one to save memory:

    >> g := combinat::integerVectors::generator(2, 2):
       g(); g(); g(); g();

                                      [2, 0]

                                      [1, 1]

                                      [0, 2]

                                       FAIL

Typically, this would be used as follows:

    >> g := combinat::integerVectors::generator(2, 2):
       while (p := g()) <> FAIL do print(p): end:

                                      [2, 0]

                                      [1, 1]

                                      [0, 2]

#### Example 2

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

    >> combinat::integerVectors::list(4, 3, MaxPart=2)

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

             [0, 2, 2]]

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

    >> combinat::integerVectors::list(4, 3, MinPart=1)

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

#### Example 3

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

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

              [[3, 1, 0], [3, 0, 1], [2, 1, 1], [2, 0, 2], [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 the integer vectors of sum 4 and of length at most 3 such that the first and third parts are at most 1:

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

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

This is the list of the integer vectors of sum 4 lower bounded by `[1, 1, 1]`:

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

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

#### Example 4

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 integer vectors of sum 4 with 3 parts:

    >> combinat::integerVectors::list(4, 3, MinSlope=0)

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

This is the list of the integer vectors of sum 4 with 3 parts such that two consecutive parts differ by at most one unit:

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

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

#### Example 5

The constraints can be combined together in all reasonable ways. This is the list of the integer vectors of sum 11 with 3 parts between 2 and 5 such that the difference between two consecutive parts is between -2 and 2:

    >> combinat::integerVectors::list(11, 3,
                                      MinSlope=-2, MaxSlope=2,
                                      MinPart=2, MaxPart=5)

          [[5, 4, 2], [5, 3, 3], [4, 4, 3], [4, 3, 4], [3, 5, 3],

             [3, 4, 4], [3, 3, 5], [2, 4, 5]]

Idem with an Outer constraint:

    >> combinat::integerVectors::list(11, 3,
                                      MinSlope=-2, MaxSlope=2,
                                      MinPart=2, MaxPart=5,
                                      Outer=[4,5,4])

                   [[4, 4, 3], [4, 3, 4], [3, 5, 3], [3, 4, 4]]

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

    >> combinat::integerVectors::list(5, 3, Inner=[2, 0, 2], MinPart=2)

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

#### Example 6

We demonstrate how to generate the monomials in the variables `x,y,z` of total degree 6 which are divisible by `x^2z` and divide `x^5yz^2`

    >> map(combinat::integerVectors::list(6, 3, Inner=[2,0,1],
       Outer=[5,1,2]), v -> expr(poly([[1,v]], [x,y,z])))

                            5     4       4  2   3    2
                          [x  z, x  y z, x  z , x  y z ]

#### Example 7

We demonstrate how to generate the Motzkin words of a given length `k`. A Motzkin word is a list of -1, 0, and 1 of length `n` such that all partial sums are nonnegative and the total sum is zero. Geometrically, this is a discrete path in the integer plane N×N starting at (0,0) with right-down, right and right-up steps, and ending at (n,0). We work on the list of the `k+1` partial sums, and use the option Outer to force the first and last one to be zero. Note that Outer itself is required to satisfy the slope constraints. We also disregard the sum `s` of the partial sums. Here is the list of the Motzkin words of length 5:

    >> map(_concat(combinat::integerVectors::list(s, 5,
                             MinSlope=-1, MaxSlope=1,
                             Outer=[0, 1, 2, 1, 0]) $ s=0..4),
           l -> [l[i+1]-l[i] $ i=1..nops(l)-1])

          [[0, 0, 0, 0], [1, -1, 0, 0], [0, 1, -1, 0], [0, 0, 1, -1],

             [1, 0, -1, 0], [1, -1, 1, -1], [0, 1, 0, -1],

             [1, 0, 0, -1], [1, 1, -1, -1]]

A similar trick can be used to generate Dyck words instead. Here is the list of Dyck words of length 2×4:

    >> map(_concat(combinat::integerVectors::list(s, 9,
                              MinSlope=0, MaxSlope=1,
                              Inner=[0, 1, 1, 2, 2, 3, 3, 4, 4],
                              Outer=[0, 1, 2, 3, 4, 4, 4, 4, 4]
                                      ) $ s=20..26),
           l -> combinat::dyckWords::toString
             ([if l[i+1]=l[i] then 0 else 1 end_if $ i=1..nops(l)-1]))

          ["()()()()", "(())()()", "()(())()", "()()(())", "(()())()",

             "(())(())", "()(()())", "((()))()", "(()()())", "()((()))",

             "((())())", "(()(()))", "((()()))", "(((())))"]

#### Example 8

We show here how to generate the ordered `k`-partitions of an integer vector `m`; that is the lists of `k` integer vectors `m1,...,mk` such that `m1+...+mk=m`; or the `k x nops(m)` matrix with prescribed column sums given by `m`.

We can build for each part `m[i]` of `m` a generator for the integer vectors of sum `m[i]` with `k` parts, and take the cartesian product of those generators. Note that this yields lists of `l` lists of `k` integers instead of lists of `k` lists of `l` integers, so we need to further transpose the lists.

Let's take an example, with `m:=[1,3,2]` and `k:=2`. The first part yields the lists `[1,0]` or `[0,1]`, the second `[3,0]`, `[2,1]`, `[1,2]`, or `[0,3]` and the last part yields `[2,0]`, `[1,1]`, `[0,2]`. The first element of the cartesian product is `[[1,0], [3,0],[2,0]]`, and after transposition we get `[[1,3,2],[0,0,0]]`.

Now, here is the code:

    >> orderedIntegerVectorPartitionsGenerator :=
       proc(m: combinat::integerVectors, k: Type::PosInt)
           option escape;
       begin
           combinat::generators::map
           (// The cartesian product of the generators of integer vectors
            combinat::generators::cartesian
       	(combinat::integerVectors::generator(m[i], k) $ i=1..nops(m)),
            // A function that does the transposition
            l->[[l[j][i] $ j=1..nops(m)] $ i=1..k]);
       end_proc:
       g := orderedIntegerVectorPartitionsGenerator([1,3,2], 2):
       g(), g(), g(), g(), g();

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

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

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

Alltogether, there are `2*4*3=24` ordered 2-partitions of `[1,3,2]`:

    >> g := orderedIntegerVectorPartitionsGenerator([1,3,2], 2):
       combinat::generators::count(g);

                                        24

As an application, this can be used to generate the ordered `k`-partitions of a multiset `s`; that is the lists of `k` multisets `s1,...,sk` whose union is `s`; for example, `[{a,b,b,b,c}, {a,b,d}]` and `[{a,b,d}, {a,b,b,b,c}]` are two distinct partitions of the multiset `{a,a,b,b,b,b,c,d}`.

Indeed, a multiset `s` such as `{a,a,b,b,b,b,c,d}` can be represented by the integer vector `m` of its repetitions, here `[2,4,1,1]`. Now, partitioning `s` in `k` multisets is equivalent to finding `k` integer vectors `m1,...,mk` that sum up to `m` as above. We leave as an exercise for the reader to build the appropriate conversion routines and to derive a generator for ordered multiset partitions (hint: use `combinat::generators::map`).

#### Background

- Integer vectors are naturally ordered lexicographically. The functions for counting and generating are directly inherited from `Cat::IntegerListsLexClass` with `Length=k`. The complexity of the generation algorithm is constant time amortized for each integer vector generated.

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

#### Super-Domain

`combinat::words`

#### Axioms

`Ax::systemRep`

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package