Bounded Composition - Maple Help

Iterator

 BoundedComposition
 generate bounded compositions that sum to a constant

 Calling Sequence BoundedComposition(M, T, opts)

Parameters

 M - {list,Vector,Array}(nonnegint); bounds of components of each composition T - nonnegint; sum of each composition opts - (optional) equation(s) of the form option = value; specify options for the BoundedComposition command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.

Description

 • The BoundedComposition command returns an iterator that generates bounded compositions in reverse lexicographic order.
 • A bounded composition is a sequence of integers, $\left({r}_{1},\dots ,{r}_{n}\right)$, such that $T=\sum _{k=1}^{n}{r}_{k}$ and $0\le {r}_{k}\le {M}_{k}$, for $k\in \left\{1\dots n\right\}$, with $n=\mathrm{numelems}\left(M\right)$.
 • A bounded composition with $M=\left[{m}_{1},{m}_{2},\dots ,{m}_{n}\right]$ and sum $T$ is equivalent to a multicombination of $T$ elements chosen from a multiset of $n$ distinct elements with ${m}_{k}$ the multiplicity of the $k$-th element.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$
 > $B≔\mathrm{BoundedComposition}\left(\left[5,2,4\right],8\right):$
 > $\mathrm{Print}\left(B,'\mathrm{showrank}'\right):$
 1: 5 2 1 2: 5 1 2 3: 4 2 2 4: 5 0 3 5: 4 1 3 6: 3 2 3 7: 4 0 4 8: 3 1 4 9: 2 2 4

Contingency Table

 • A contingency table is an $m×n$ matrix of nonnegative integers $\left({a}_{\mathrm{ij}}\right)$ with given row sums ${R}_{i}=\sum _{j=1}^{n}{a}_{\mathrm{ij}}$ and column sums ${C}_{j}=\sum _{i=1}^{m}{a}_{\mathrm{ij}}$. Given the $m$-vector $R$ and $n$-vector $C$, we want to compute the number of distinct contingency tables. Use a bounded-composition with $M=C$ and $T={R}_{1}$ to generate a valid first row. Use a bounded-composition with $M=C-\sum _{k=1}^{i-1}{r}_{k}$ and $T={R}_{i}$, where ${r}_{k}$ is the content of the $k$-th row, to generate a valid $i$-th row. The last row is fixed by preceding rows. The following procedure uses a recursive procedure, cnt, to generate and enumerate the iterators for each row.
 > Cnt := proc(R :: ~Array, C :: ~Array) local cnt,m;     if add(R) <> add(C) then         error "row and column sums must be equal";     end if;     m := numelems(R);     cnt := proc(i, c)     local r;         if i = m then             return 1;  # final row         else             add(cnt(i+1, c-r), r = BoundedComposition(c,R[i]));         end if;     end proc;     cnt(1, C); end proc:
 • Try it with a known case (value must be 5!).
 > $\mathrm{Cnt}\left(\mathrm{}\left(\left[\mathrm{}\left(1,5\right)\right],2\right)\right)$
 ${120}$ (1)
 • Try a simple case
 > $\mathrm{Cnt}\left(\left[2,3,4\right],\left[1,3,5\right]\right)$
 ${24}$ (2)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions,sec. 7.2.1.3, exercise 60, p. 30, and answers, algorithm Q, pp. 98-99.

Compatibility

 • The Number method was updated in Maple 2020.
 • The Iterator[BoundedComposition] command was introduced in Maple 2016.