Editing Combinatorial number system (section)


In [[mathematics]], and in particular in [[combinatorics]], the '''combinatorial number system''' of degree ''k'' (for some positive [[integer]] ''k''), also referred to as '''combinadics''', or the '''Macaulay representation of an integer''', is a correspondence between [[natural number]]s (taken to include&nbsp;0) ''N'' and ''k''-[[combination]]s. The combinations are represented as [[Sequence#Increasing and decreasing|strictly decreasing]] [[integer sequence|sequences]] ''c''<sub>''k''</sub>&nbsp;&gt;&nbsp;...&nbsp;&gt;&nbsp;''c''<sub>2</sub>&nbsp;&gt;&nbsp;''c''<sub>1</sub>&nbsp;≥&nbsp;0 where each ''c<sub>i</sub>'' corresponds to the index of a chosen element in a given ''k''-combination. Distinct numbers correspond to distinct ''k''-combinations, and produce them in [[lexicographic order]]. The numbers less than <math>\tbinom nk</math> correspond to all {{nowrap|''k''-combinations}} of {{nowrap|{0, 1, ..., ''n'' − 1}}}. The correspondence does not depend on the size&nbsp;''n'' of the set that the ''k''-combinations are taken from, so it can be interpreted as a map from '''N''' to the ''k''-combinations taken from '''N'''; in this view the correspondence is a [[bijective map|bijection]].

The number ''N'' corresponding to (''c''<sub>''k''</sub>, ..., ''c''<sub>2</sub>, ''c''<sub>1</sub>) is given by

:<math>N=\binom{c_k}k+\cdots+\binom{c_2}2+\binom{c_1}1</math>.

The fact that a unique sequence corresponds to any non-negative number ''N'' was first observed by [[Derrick Henry Lehmer|D. H. Lehmer]].<ref>''Applied Combinatorial Mathematics'', Ed. E. F. Beckenbach (1964), pp.27−30.</ref> Indeed, a [[greedy algorithm]] finds the ''k''-combination corresponding to ''N'': take ''c''<sub>''k''</sub> maximal with <math>\tbinom{c_k}k\leq N</math>, then take ''c''<sub>''k''−1</sub> maximal with <math>\tbinom{c_{k-1}}{k-1}\leq N - \tbinom{c_k}k</math>, and so forth. Finding the number ''N'', using the formula above, from the ''k''-combination (''c''<sub>''k''</sub>, ..., ''c''<sub>2</sub>, ''c''<sub>1</sub>) is also known as "ranking", and the opposite operation (given by the greedy algorithm) as "unranking"; the operations are known by these names in most [[computer algebra system]]s, and in [[computational mathematics]].<ref>[http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf Generating Elementary Combinatorial Objects], Lucia Moura, U. Ottawa, Fall 2009</ref><ref>{{Cite web|url=https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/combination.html|title = Combinations — Sage 9.4 Reference Manual: Combinatorics}}</ref>

The originally used term "combinatorial representation of integers" was shortened to "combinatorial number system" by [[Donald Ervin Knuth|Knuth]],<ref>{{citation
| last=Knuth | first = D. E. | author-link = Donald Ervin Knuth
| title = [[The Art of Computer Programming]]
| volume =4, Fascicle 3
| contribution = Generating All Combinations and Partitions | publisher = Addison-Wesley | year = 2005
| isbn = 0-201-85394-9
| pages = 5−6}}.</ref>
who also gives a much older reference;<ref>{{citation
| last = Pascal | first = Ernesto | title=Giornale di Matematiche | volume = 25 | year = 1887 | pages = 45−49}}</ref>
the term "combinadic" is introduced by James McCaffrey<ref>{{citation
 | last = McCaffrey | first = James | author-link = James D. McCaffrey
 | publisher = Microsoft Developer Network
 | title = Generating the mth Lexicographical Element of a Mathematical Combination
 | url = https://docs.microsoft.com/en-us/previous-versions/visualstudio/aa289166(v=vs.70)
 | year = 2004}}</ref> (without reference to previous terminology or work).

Unlike the [[factorial number system]], the combinatorial number system of degree ''k'' is not a [[mixed radix]] system: the part <math>\tbinom{c_i}i</math> of the number ''N'' represented by a "digit" ''c''<sub>''i''</sub> 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 the ''k''-combination that is at a given position in the lexicographic ordering, without having to explicitly list the {{nowrap|''k''-combinations}} preceding it; this allows for instance random generation of ''k''-combinations of a given set. [[Enumerative combinatorics|Enumeration of ''k''-combinations]] has many applications, among which are [[software testing]], [[sampling (statistics)|sampling]], [[quality control]], and the analysis of [[lottery]] games.