Iterator
BoundedComposition
generate bounded compositions that sum to a constant
Calling Sequence
Parameters
Options
Description
Examples
References
Compatibility
BoundedComposition(M, T, opts)
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
compile = truefalse
True means compile the iterator. The default is true.
The BoundedComposition command returns an iterator that generates bounded compositions in reverse lexicographic order.
A bounded composition is a sequence of integers, r1,…,rn, such that T=∑k=1nrk and 0≤rk≤Mk, for k∈1…n, with n=numelems⁡M.
A bounded composition with M=m1,m2,…,mn and sum T is equivalent to a multicombination of T elements chosen from a multiset of n distinct elements with mk the multiplicity of the k-th element.
with⁡Iterator:
B≔BoundedComposition⁡5,2,4,8:
Print⁡B,showrank:
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 aij with given row sums Ri=∑j=1naij and column sums Cj=∑i=1maij. 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=R1 to generate a valid first row. Use a bounded-composition with M=C−∑k=1i−1rk and T=Ri, where rk 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!).
Cnt⁡`$`⁡`$`⁡1,5,2
120
Try a simple case
Cnt⁡2,3,4,1,3,5
24
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.
The Number method was updated in Maple 2020.
The Iterator[BoundedComposition] command was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
See Also
combinat[choose]
Download Help Document