Movatterモバイル変換

[0]ホーム

Jump to content

Combinatorial number system

Português

Edit links

From Wikipedia, the free encyclopedia

Numbering of combinations of items

The ${\tbinom {5}{3}}=10$ rows of this matrix are the3-combinations of $\{0...4\}$ . When ${\color {Red}n}$ is the ${\color {Green}k}$ -th element of the combination, the "digit" is ${\tbinom {\color {Red}n}{\color {Green}k}}$ .

{\displaystyle {\tbinom {5}{3}}=10} — The ${\tbinom {5}{3}}=10$ rows of this matrix are the3-combinations of $\{0...4\}$ . When ${\color {Red}n}$ is the ${\color {Green}k}$ -th element of the combination, the "digit" is ${\tbinom {\color {Red}n}{\color {Green}k}}$ .

The last 3-combination of $\{0...9\}$ has number ${\tbinom {\color {Red}7}{\color {Green}1}}+{\tbinom {\color {Red}8}{\color {Green}2}}+{\tbinom {\color {Red}9}{\color {Green}3}}=119$ , which is ${\tbinom {10}{3}}-1$ .

{\displaystyle \{0...9\}} — The last 3-combination of $\{0...9\}$ has number ${\tbinom {\color {Red}7}{\color {Green}1}}+{\tbinom {\color {Red}8}{\color {Green}2}}+{\tbinom {\color {Red}9}{\color {Green}3}}=119$ , which is ${\tbinom {10}{3}}-1$ .

{0,3,4,6,9} and {0,1,3,7,9}

Ernesto Pascal (1887): An integer $N {\displaystyle N}$ has a unique expression as $\sum _{k=1}^{n}{\binom {x_{k}}{k}}$ with increasing $x_{k}$ .

Ernesto Pascal (1887): An integer $N {\displaystyle N}$ has a unique expression as $\sum _{k=1}^{n}{\binom {x_{k}}{k}}$ with increasing $x_{k}$ .

Inmathematics, and in particular incombinatorics, thecombinatorial number system of degreek (for some positiveintegerk), also referred to ascombinadics, or theMacaulay representation of an integer, is a correspondence betweennatural numbers (taken to include 0)N andk-combinations. The combinations are represented asstrictly decreasing sequencesc_k > ... > c₂ > c₁ ≥ 0 where eachc_i corresponds to the index of a chosen element in a givenk-combination. Distinct numbers correspond to distinctk-combinations, and produce them inlexicographic order. The numbers less than ${\tbinom {n}{k}}$ correspond to allk-combinations of{0, 1, ...,n − 1}. The correspondence does not depend on the size n of the set that thek-combinations are taken from, so it can be interpreted as a map fromN to thek-combinations taken fromN; in this view the correspondence is abijection.

The numberN corresponding to (c_k, ...,c₂,c₁) is given by

N={\binom {c_{k}}{k}}+\cdots +{\binom {c_{2}}{2}}+{\binom {c_{1}}{1}}

The fact that a combination corresponds to a non-negative integer was observed byLehmer (1964).^[1] Indeed, agreedy algorithm finds thek-combination corresponding toN: takec_k maximal with ${\tbinom {c_{k}}{k}}\leq N$ , then takec_k−1 maximal with ${\tbinom {c_{k-1}}{k-1}}\leq N-{\tbinom {c_{k}}{k}}$ , and so forth. Finding the numberN, using the formula above, from thek-combination (c_k, ...,c₂,c₁) is also known as "ranking", and the opposite operation (given by the greedy algorithm) as "unranking"; the operations are known by these names in mostcomputer algebra systems, and incomputational mathematics.^[2]^[3]

The term "combinatorial representation of integers" was shortened to "combinatorial number system" byKnuth (2011).^[4]He also referencesErnesto Pascal (1887).^[5]The term "combinadic" is introduced by James McCaffrey.^[6]

Unlike thefactorial number system, the combinatorial number system of degreek is not amixed radix system: the part ${\tbinom {c_{i}}{i}}$ of the numberN represented by a "digit"c_i is not obtained from it by simply multiplying by a place value.

The main application of the combinatorial number system is that it allows rapid computation of thek-combination that is at a given position in the lexicographic ordering, without having to explicitly list thek-combinations preceding it; this allows for instance random generation ofk-combinations of a given set.Enumeration ofk-combinations has many applications, among which aresoftware testing,sampling,quality control, and the analysis oflottery games.

Ordering combinations

[edit]

Ak-combination of a setS is asubset ofS withk (distinct) elements. The main purpose of the combinatorial number system is to provide a representation, each by a single number, of all ${\tbinom {n}{k}}$ possiblek-combinations of a setS ofn elements. Choosing, for anyn,{0, 1, ...,n − 1} as such a set, it can be arranged that the representation of a givenk-combinationC is independent of the value ofn (althoughn must of course be sufficiently large); in other words consideringC as a subset of a larger set by increasingn will not change the number that represents C. Thus for the combinatorial number system one just considersC as ak-combination of the setN of all natural numbers, without explicitly mentioningn.

In order to ensure that the numbers representing thek-combinations of{0, 1, ...,n − 1} are less than those representingk-combinations not contained in{0, 1, ...,n − 1}, thek-combinations must be ordered in such a way that their largest elements are compared first. The most natural ordering that has this property islexicographic ordering of thedecreasing sequence of their elements. So comparing the 5-combinationsC = {0,3,4,6,9} andC′ = {0,1,3,7,9}, one has thatC comes beforeC′, since they have the same largest part 9, but the next largest part 6 ofC is less than the next largest part 7 ofC′; the sequences compared lexicographically are (9,6,4,3,0) and (9,7,3,1,0).

Another way to describe this ordering is view combinations as describing thek raised bits in thebinary representation of a number, so thatC = {c₁, ...,c_k} describes the number

2^{c_{1}}+2^{c_{2}}+\cdots +2^{c_{k}}

(this associates distinct numbers toall finite sets of natural numbers); then comparison ofk-combinations can be done by comparing the associated binary numbers. In the exampleC andC′ correspond to numbers 1001011001₂ = 601₁₀ and 1010001011₂ = 651₁₀, which again shows thatC comes beforeC′. This number is not however the one one wants to represent thek-combination with, since many binary numbers have a number of raised bits different fromk; one wants to find the relative position ofC in the ordered list of (only)k-combinations.

Place of a combination in the ordering

[edit]

The number associated in the combinatorial number system of degreek to ak-combinationC is the number ofk-combinations strictly less thanC in the given ordering. This number can be computed fromC = {c_k, ...,c₂,c₁} withc_k > ... >c₂ >c₁ as follows.

From the definition of the ordering it follows that for eachk-combinationS strictly less than C, there is a unique index i such thatc_i is absent fromS, whilec_k, ...,c_i+1 are present inS, and no other value larger thanc_i is. One can therefore group thosek-combinationsS according to the possible values 1, 2, ...,k ofi, and count each group separately. For a given value ofi one must includec_k, ...,c_i+1 inS, and the remainingi elements ofS must be chosen from thec_i non-negative integers strictly less thanc_i; moreover any such choice will result in ak-combinationsS strictly less than C. The number of possible choices is ${\tbinom {c_{i}}{i}}$ , which is therefore the number of combinations in groupi; the total number ofk-combinations strictly less thanC then is

{\binom {c_{1}}{1}}+{\binom {c_{2}}{2}}+\cdots +{\binom {c_{k}}{k}},

and this is the index (starting from 0) ofC in the ordered list ofk-combinations.

Obviously there is for everyN ∈ N exactly onek-combination at index N in the list (supposingk ≥ 1, since the list is then infinite), so the above argument proves that everyN can be written in exactly one way as a sum ofk binomial coefficients of the given form.

Finding thek-combination for a given number

[edit]

The given formula allows finding the place in the lexicographic ordering of a givenk-combination immediately. The reverse process of finding thek-combination at a given placeN requires somewhat more work, but is straightforward nonetheless. By the definition of the lexicographic ordering, twok-combinations that differ in their largest elementc_k will be ordered according to the comparison of those largest elements, from which it follows that all combinations with a fixed value of their largest element are contiguous in the list. Moreover the smallest combination withc_k as the largest element is ${\tbinom {c_{k}}{k}}$ , and it hasc_i = i − 1 for alli < k (for this combination all terms in the expression except ${\tbinom {c_{k}}{k}}$ are zero). Thereforec_k is the largest number such that ${\tbinom {c_{k}}{k}}\leq N$ . Ifk > 1 the remaining elements of thek-combination form thek − 1-combination corresponding to the number $N-{\tbinom {c_{k}}{k}}$ in the combinatorial number system of degreek − 1, and can therefore be found by continuing in the same way for $N-{\tbinom {c_{k}}{k}}$ andk − 1 instead ofN andk.

Example

[edit]

Suppose one wants to determine the 5-combination at position 72. The successive values of ${\tbinom {n}{5}}$ forn = 4, 5, 6, ... are 0, 1, 6, 21, 56, 126, 252, ..., of which the largest one not exceeding 72 is 56, forn = 8. Thereforec₅ = 8, and the remaining elements form the4-combination at position72 − 56 = 16. The successive values of ${\tbinom {n}{4}}$ forn = 3, 4, 5, ... are 0, 1, 5, 15, 35, ..., of which the largest one not exceeding 16 is 15, forn = 6, soc₄ = 6. Continuing similarly to search for a 3-combination at position16 − 15 = 1 one findsc₃ = 3, which uses up the final unit; this establishes $72={\tbinom {8}{5}}+{\tbinom {6}{4}}+{\tbinom {3}{3}}$ , and the remaining valuesc_i will be the maximal ones with ${\tbinom {c_{i}}{i}}=0$ , namelyc_i =i − 1. Thus we have found the 5-combination{8, 6, 3, 1, 0}.

National Lottery example

[edit]

For each of the ${\binom {49}{6}}$ lottery combinationsc₁ < c₂ < c₃ < c₄ < c₅ < c₆ , there is a list numberN between 0 and ${\binom {49}{6}}-1$ which can be found by adding

{\binom {49-c_{1}}{6}}+{\binom {49-c_{2}}{5}}+{\binom {49-c_{3}}{4}}+{\binom {49-c_{4}}{3}}+{\binom {49-c_{5}}{2}}+{\binom {49-c_{6}}{1}}.

References

[edit]

^Applied Combinatorial Mathematics, Ed. E. F. Beckenbach (1964), pp.27−30.
^Generating Elementary Combinatorial Objects, Lucia Moura, U. Ottawa, Fall 2009
^"Combinations — Sage 9.4 Reference Manual: Combinatorics".
^Knuth, D. E. (2005), "Generating All Combinations and Partitions",The Art of Computer Programming, vol. 4, Fascicle 3, Addison-Wesley, pp. 5−6,ISBN 0-201-85394-9.
^Pascal, Ernesto (1887),Giornale di Matematiche, vol. 25, pp. 45−49
^McCaffrey, James (2004),Generating the mth Lexicographical Element of a Mathematical Combination, Microsoft Developer Network

Movatterモバイル変換

Combinatorial number system

Ordering combinations

Place of a combination in the ordering

Finding thek-combination for a given number

Example

National Lottery example

See also

References

Further reading