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, , 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!).

(1)
• 

Try a simple case

(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

 


Download Help Document