combinat - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : combinat : combinat/rankcomb

combinat

 rankcomb
 compute the lexicographic rank of a given combination
 unrankcomb
 compute the combination with a given lexicographic rank

 Calling Sequence rankcomb( s, n ) unrankcomb( r, n, k )

Parameters

 s - set(posint); a set of positive integers from 1 to n for some n n - posint; size of the set from which combination members are chosen k - posint; size of the combination r - posint; the rank of a combination

Description

 • Given a combination (subset) s of the integers from 1 to n, for some positive integer n, the command rankcomb( 's', 'n' ) computes the lexicographic rank of s.  That is, if s has k members, and if the k-subsets of {1,2,...,n} are listed lexicographically, then the position of the given subset in this ordered list is returned.
 • Given a rank r (where r is at most binomial(n,k)), the command unrankcomb( 'r', 'n', 'k' ) computes the k-subset of {1,2,...,n} which occurs in the r-th place in a lexicographically ordered list of the k-subsets of {1,2,...,n}.
 • The commands rankcomb and unrankcomb are inverse to one another in the sense that they satisfy rankcomb( unrankcomb( r, k, n ), n ) = r and unrankcomb( rankcomb( s, n ), nops( s ), n ) = s.

 • The combinat[rankcomb] and combinat[unrankcomb] commands are thread-safe as of Maple 16.

Examples

 > $\mathrm{with}\left(\mathrm{combinat}\right):$
 > $\mathrm{rankcomb}\left(\left\{2,3,4\right\},5\right)$
 ${7}$ (1)
 > $\mathrm{rankcomb}\left(\left\{2,3,4\right\},9\right)$
 ${29}$ (2)
 > $\mathrm{unrankcomb}\left(29,9,3\right)$
 $\left\{{2}{,}{3}{,}{4}\right\}$ (3)

Compatibility

 • The combinat[rankcomb] and combinat[unrankcomb] commands were introduced in Maple 16.