% $Id: integerVectorsWeighted.tex,v 1.1.1.6 2004/10/04 17:25:16 nthiery Exp $
\begin{Mhelppage}{integerVectorsWeighted}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{teresa}{10/2003}{proofread}

\begin{MInfo}
  \eng{weighted integer vectors}
\end{MInfo}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating weighted integer vectors.}
\end{MIntro}

\MKeywords{combinatorics,integerVector}

\begin{MDetails}
  \eng{Let \Mpar{w} be a \emph{vector of weights}, i.e. a list of \Mpar{k}
    positive integers, and let \Mpar{n} be a nonnegative integer. A
    \Mpar{w}-\emph{weighted integer vector} of sum \Mpar{n} is a list
    \Mex{v} of \Mpar{k} nonnegative integers such that
    \Mdmath{c[1]*w[1] + ... + c[k]*w[k] = n.}{c_1w_1+\dots+c_kw_k=n.}
    
    For example, \Mex{[1,2,0]} is a \Mex{[3,1,1]}-weighted integer
    vector of sum $5$.}
  
  \eng{If \Mmath{w[1]=...=w[k]=1}{w_1=\dots=w_k=1}, then a
    \Mpar{w}-weighted integer vector of sum \Mpar{n} is an
    integer vector of sum \Mpar{n}; we suggest to use the much faster
    \Mup{combinat::integerVectors} library in this case.}
  
  \eng{If \Mex{x[1],...,x[k]} are variables with degree given by
    \Mex{w[1],...,w[k]} then a \Mpar{w}-weighted integer vector of sum
    \Mpar{n} is the exponent vector of a monomial of total degree \Mpar{n}
    in those variables.}
\end{MDetails}

\begin{MCategories}
\Mup{Cat::CombinatorialClass}
\end{MCategories}

\MRelatedDomains{combinat::integerVectors}

\begin{MDomEntries}
  \MDomEntry{domtype}
  \eng{The \mupad\ domain used to represent weighted integer vectors: \Mup{DOM_LIST}}
\end{MDomEntries}

\begin{MMethodDetails}{count}
  \infoEng{number of weighted integer vectors}%
  \call{\Mtype{nonnegative integer} n, \Mtype{weight vector} w}%
  \eng{Returns the number of \Mpar{w}-weighted integer vectors of sum
    \Mpar{n}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the weighted integer vectors}%
  \call{\Mtype{nonnegative integer} n, \Mtype{weight vector} w}%
  \eng{Returns the list of the \Mpar{w}-weighted integer vectors of
    sum \Mpar{n}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for weighted integer vectors}%
  \call{\Mtype{nonnegative integer} n, \Mtype{weight vector} w}%
  \eng{Returns a generator for the \Mpar{w}-weighted integer vectors
    of sum \Mpar{n}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generatingSeries}
  \infoEng{generating series for weighted integer vectors}%
  \call{\Mtype{weight vector} w \Mopt{, \Mtype{indeterminate} z = z}}%
  \eng{Returns the generating series in \Mpar{z} for the
    \Mpar{w}-weighted integer vectors by sum.}
\end{MMethodDetails}

\begin{MExample}{ex-basic}
  \eng{There are $5$ \Mex{[3,1,2]}-weighted integer vectors of sum $5$:}
  \begin{Mexin}
combinat::integerVectorsWeighted::count(5, [3,1,2])
  \end{Mexin}
  \begin{Mexout}
                               5
  \end{Mexout}

  \eng{Here is the list:}
  \begin{Mexin}
combinat::integerVectorsWeighted::list(5, [3,1,2])
  \end{Mexin}
  \begin{Mexout}
    [[1, 0, 1], [1, 2, 0], [0, 1, 2], [0, 3, 1], [0, 5, 0]]
  \end{Mexout}
  
  \eng{Finally, this is the generating series for the
    \Mex{[3,1,2]}-weighted integer vectors:}
  \begin{Mexin}
combinat::integerVectorsWeighted::generatingSeries([3,1,2]);
series(%,z)
  \end{Mexin}
  \begin{Mexout}
                                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 )
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-applications}
  We search for all the ways to pay a $17$ cents postal fee using
  stamps of $3$, $4$, and $5$ cents:
  \begin{Mexin}
combinat::integerVectorsWeighted(17,[3,4,5]);
  \end{Mexin}
  \begin{Mexout}
         [[1, 1, 2], [0, 3, 1], [4, 0, 1], [3, 2, 0]]
  \end{Mexout}
  Another approach is to look for the partitions of $17$ including
  only $3$, $4$, and $5$. This is easily done by:
  \begin{Mexin}
combinat::partitions::list(17,MinPart=3,MaxPart=5);
  \end{Mexin}
  \begin{Mexout}
[[5, 5, 4, 3], [5, 4, 4, 4], [5, 3, 3, 3, 3], [4, 4, 3, 3, 3]]
  \end{Mexout}
\end{MExample}

\begin{MBackground}
  \eng{\Mwarn{This library uses a crude backtrack algorithm with
      simple heuristics; this can be slow!}}
\end{MBackground}

\MSuperDomain{Dom::BaseDomain}
 
\begin{MAxioms}
  \Mup{Ax::systemRep}
\end{MAxioms}

\begin{MChanges}
  \version{2.5}%
  \eng[New library]{\Mthis{} is a new library}
  \version{3.0}%
  \eng{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.}
\end{MChanges}

\end{Mhelppage}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: main
%%% End: 
