[Previous] [Next] [Contents]

## `combinat::integerVectorsWeighted` -- weighted integer vectors

#### Introduction

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

#### Details

- Let `w` be a vector of weights, i.e. a list of `k` positive integers, and let `n` be a nonnegative integer. A `w`-weighted integer vector of sum `n` is a list `v` of `k` nonnegative integers such that

      c[1]*w[1] + ... + c[k]*w[k] = n.

  For example, `[1,2,0]` is a `[3,1,1]`-weighted integer vector of sum 5.

- If w[1]=...=w[k]=1, then a `w`-weighted integer vector of sum `n` is an integer vector of sum `n`; we suggest to use the much faster `combinat::integerVectors` library in this case.

- If `x[1],...,x[k]` are variables with degree given by `w[1],...,w[k]` then a `w`-weighted integer vector of sum `n` is the exponent vector of a monomial of total degree `n` in those variables.

#### Categories

`Cat::CombinatorialClass`

#### Related Domains

`combinat::integerVectors`

#### Entries

domtype

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

#### Method count: number of weighted integer vectors

- `count(nonnegative integer n, weight vector w)`

- Returns the number of `w`-weighted integer vectors of sum `n`.

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

- `list(nonnegative integer n, weight vector w)`

- Returns the list of the `w`-weighted integer vectors of sum `n`.

#### Method generator: generator for weighted integer vectors

- `generator(nonnegative integer n, weight vector w)`

- Returns a generator for the `w`-weighted integer vectors of sum `n`.

#### Method generatingSeries: generating series for weighted integer vectors

- `generatingSeries(weight vector w <, indeterminate z = z>)`

- Returns the generating series in `z` for the `w`-weighted integer vectors by sum.

#### Example 1

There are 5 `[3,1,2]`-weighted integer vectors of sum 5:

    >> combinat::integerVectorsWeighted::count(5, [3,1,2])

                                         5

Here is the list:

    >> combinat::integerVectorsWeighted::list(5, [3,1,2])

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

Finally, this is the generating series for the `[3,1,2]`-weighted integer vectors:

    >> combinat::integerVectorsWeighted::generatingSeries([3,1,2]);
       series(%,z)

                                          1
                            - -------------------------
                                2        3
                              (z  - 1) (z  - 1) (z - 1)

                                2      3      4      5      6
                     1 + z + 2 z  + 3 z  + 4 z  + 5 z  + O(z )

#### Example 2

We search for all the ways to pay a 17 cents postal fee using stamps of 3, 4, and 5 cents:

    >> combinat::integerVectorsWeighted(17,[3,4,5]);

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

Another approach is to look for the partitions of 17 including only 3, 4, and 5. This is easily done by:

    >> combinat::partitions::list(17,MinPart=3,MaxPart=5);

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

#### Background

- Generating, or even testing the existence of weighted integer vectors of a given sum is a knapsack-like NP-hard problem, and this library uses a crude backtrack algorithm with simple heuristics. So functions in this library can be slow!

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

#### Changes

- The algorithm automatically sorts the weights internally, so the user does not need any more to provide a sorted list of weights to improve the efficiency.

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package