|
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
|
|
|
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, , such that and , for , with .
|
•
|
A bounded composition with and sum is equivalent to a multicombination of elements chosen from a multiset of distinct elements with the multiplicity of the -th element.
|
|
|
Examples
|
|
>
|
|
>
|
|
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 matrix of nonnegative integers with given row sums and column sums . Given the -vector and -vector , we want to compute the number of distinct contingency tables. Use a bounded-composition with and to generate a valid first row. Use a bounded-composition with and , where is the content of the -th row, to generate a valid -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!).
|
>
|
|
>
|
|
|
|
|
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.
|
|
|
|