combinat::integerVectorsWeighted
--
weighted integer vectors
The library combinat::integerVectorsWeighted
provides functions for counting,
generating, and manipulating weighted integer vectors.
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.
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.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.Cat::CombinatorialClass
The MuPAD domain used to represent weighted integer vectors: DOM_LIST
count(nonnegative integer n, weight vector w)
w
-weighted integer vectors of sum
n
.
list(nonnegative integer n, weight vector w)
w
-weighted integer vectors of
sum n
.
generator(nonnegative integer n, weight vector w)
w
-weighted integer vectors
of sum n
.
generatingSeries(weight vector w <, indeterminate z = z>)
z
for the
w
-weighted integer vectors by sum.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 )
>> 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]]
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!
Ax::systemRep
MuPAD Combinat, an open source algebraic combinatorics package