BoundedComposition - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


Iterator

  

BoundedComposition

  

generate bounded compositions that sum to a constant

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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, r1,,rn, such that T=k=1nrk and 0rkMk, for k1n, with n=numelemsM.

• 

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.

Examples

withIterator:

BBoundedComposition5,2,4,8:

PrintB,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=Ck=1i1rk 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&comma;5&comma;2

120

(1)
• 

Try a simple case

Cnt2&comma;3&comma;4&comma;1&comma;3&comma;5

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.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

combinat[choose]

Iterator