MultiCombination - Maple Help

Iterator

 MultiCombination
 generate multicombinations

 Calling Sequence MultiCombination(M, t, opts)

Parameters

 M - list(nonnegint); numbers of distinct elements t - nonnegint; size of combinations opts - (optional) equation(s) of the form option = value; specify options for the MultiCombination command

Options

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

Description

 • The MultiCombination command returns an iterator that generates all t-combinations chosen from a multiset.
 • The M parameter specifies the multiset. It is a list of nonnegative integers, $\left[{m}_{1},{m}_{2},\dots ,{m}_{n}\right]$, with ${m}_{k}$ the multiplicity of the $k$-th element. If ${m}_{k}=0$, $k$ will not appear in the output Array.
 • The t parameter is the number of items to choose.
 • The output of each iteration is an Array of t positive integers. An integer $k$ represents a selection of the $k$-th element. The elements in the Array are sorted from smallest to largest.
 • There is an isomorphism between multicombinations and bounded-compositions. This object uses the same algorithm as BoundedComposition but transforms the output.

Methods

In addition to the common iterator methods, this iterator object has the following methods. The self parameter is the iterator object.

 • Number(self): return the number of iterations required to step through the iterator, assuming it started at rank one.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$

Construct an iterator corresponding to the number of ways to choose 5 balls from a bucket with 2 red balls, 5 green balls, and 3 black balls.

 > $B≔\mathrm{MultiCombination}\left(\left[2,5,3\right],5\right):$

Print each combination. The 1s correspond to red balls, the 2s to green balls, and the 3s to black balls.

 > $\mathrm{Print}\left(B,'\mathrm{showrank}'\right):$
 1: 1 1 2 2 2  2: 1 2 2 2 2  3: 2 2 2 2 2  4: 1 1 2 2 3  5: 1 2 2 2 3  6: 2 2 2 2 3  7: 1 1 2 3 3  8: 1 2 2 3 3  9: 2 2 2 3 3 10: 1 1 3 3 3 11: 1 2 3 3 3 12: 2 2 3 3 3

Compute the number of ways to select four entrees from a menu of 10 dishes allowing multiple selections of any of the entrees. Because four is the most that can be selected, this is equivalent to assigning four as the multiplicity of all items.

 > $\mathrm{Number}\left(\mathrm{MultiCombination}\left(\left[4$10\right],4\right)\right)$  ${715}$ (1) Suppose one is allowed to choose any entree no more than twice. This can be expressed as  > $M≔\mathrm{MultiCombination}\left(\left[2$10\right],4\right):$

There are 615 ways to obtain such a combination.

 > $\mathrm{Number}\left(M\right)$
 ${615}$ (2)

Number of Distinct Ranks of a Poker Hand

 • A standard poker hand consists of five cards drawn from a 52 card deck, with four suits of 13 cards per suit.
 • The rank of a hand depends first on its category (straight flush, four of a kind, etc.), then on its rank within that category. The rank does not depend on the suits, with the exception that a flush (all five cards of the same suit) is a separate category.
 • The number of distinct hand ranks equals the number of possible flushes of a given suit plus the number of multicombinations of five cards from a deck with four cards of each rank.
 • The number of possible flushes of a given suit is simply the number of ways to choose a set of five objects from a set of thirteen distinct objects. The binomial function computes the result, $\left(\genfrac{}{}{0}{}{13}{5}\right)$. It can also be computed using the Number method of the Combination object:
 > $\mathrm{numF}≔\mathrm{Number}\left(\mathrm{Combination}\left(13,5\right)\right)$
 ${\mathrm{numF}}{≔}{1287}$ (3)
 • Construct an iterator that generates each of the multicombinations of five cards drawn from a deck.
 > $H≔\mathrm{MultiCombination}\left(\left[4$13\right],5\right):$  • Count the number of multicombinations. We can do this in a number of ways; one is simply to invoke the Number method.  > $\mathrm{numH}≔\mathrm{Number}\left(H\right)$  ${\mathrm{numH}}{≔}{6175}$ (4)  • For this case, it is also practical to count the iterations one by one.  > $\mathrm{numH}≔\mathrm{add}\left(1,h=H\right)$  ${\mathrm{numH}}{≔}{6175}$ (5)  • A final method is the following. If there were five of each ranked card, rather than four, we would obtain exactly 13 more distinct ranked hands then the actual deck (the 13 five of a kind). This is expressed by the following formula:  > $\mathrm{numH}≔\mathrm{Number}\left(\mathrm{MultiCombination}\left(\left[5$13\right],5\right)\right)-13$
 ${\mathrm{numH}}{≔}{6175}$ (6)
 • The total number of distinct ranks of poker hands is
 > $\mathrm{numF}+\mathrm{numH}$
 ${7462}$ (7)

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[MultiCombination] command was introduced in Maple 2016.