Editing Combinatorial number system


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.

== Ordering combinations ==

A ''k''-combination of a set ''S'' is a [[subset]] of ''S'' with ''k'' (distinct) elements. The main purpose of the combinatorial number system is to provide a representation, each by a single number, of all <math>\tbinom nk</math> possible ''k''-combinations of a set ''S'' of ''n'' elements. Choosing, for any ''n'', {{nowrap|{0, 1, ..., ''n''&nbsp;−&nbsp;1}}} as such a set, it can be arranged that the representation of a given ''k''-combination ''C'' is independent of the value of ''n'' (although ''n'' must of course be sufficiently large); in other words considering ''C'' as a subset of a larger set by increasing ''n'' will not change the number that represents&nbsp;''C''. Thus for the combinatorial number system one just considers ''C'' as a ''k''-combination of the set '''N''' of all natural numbers, without explicitly mentioning ''n''.

In order to ensure that the numbers representing the ''k''-combinations of {{nowrap|{0, 1, ..., ''n''&nbsp;−&nbsp;1}}} are less than those representing ''k''-combinations not contained in {{nowrap|{0, 1, ..., ''n''&nbsp;−&nbsp;1}}}, the ''k''-combinations must be ordered in such a way that their largest elements are compared first. The most natural ordering that has this property is [[lexicographic order]]ing of the ''decreasing'' sequence of their elements. So comparing the 5-combinations ''C''&nbsp;=&nbsp;{0,3,4,6,9} and ''C''′&nbsp;=&nbsp;{0,1,3,7,9}, one has that ''C'' comes before ''C''′, since they have the same largest part&nbsp;9, but the next largest part&nbsp;6 of ''C'' is less than the next largest part&nbsp;7 of ''C''′; 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 the ''k'' raised bits in the [[binary representation]] of a number, so that ''C''&nbsp;=&nbsp;{''c''<sub>1</sub>, ..., ''c''<sub>''k''</sub>} describes the number
:<math>2^{c_1}+2^{c_2}+\cdots+2^{c_k}</math>
(this associates distinct numbers to ''all'' finite sets of natural numbers); then comparison of ''k''-combinations can be done by comparing the associated binary numbers. In the example ''C'' and ''C''′ correspond to numbers 1001011001<sub>2</sub>&nbsp;=&nbsp;601<sub>10</sub> and 1010001011<sub>2</sub>&nbsp;=&nbsp;651<sub>10</sub>, which again shows that ''C'' comes before ''C''′. This number is not however the one one wants to represent the ''k''-combination with, since many binary numbers have a number of raised bits different from ''k''; one wants to find the relative position of ''C'' in the ordered list of (only) {{nowrap|''k''-combinations}}.

== Place of a combination in the ordering ==

The number associated in the combinatorial number system of degree ''k'' to a ''k''-combination ''C'' is the number of ''k''-combinations strictly less than ''C'' in the given ordering. This number can be computed from ''C''&nbsp;=&nbsp;{''c''<sub>''k''</sub>, ..., ''c''<sub>2</sub>, ''c''<sub>1</sub>} with ''c''<sub>''k''</sub>&nbsp;&gt;&nbsp;...&nbsp;&gt; ''c''<sub>2</sub> &gt; ''c''<sub>1</sub> as follows.

From the definition of the ordering it follows that for each ''k''-combination ''S'' strictly less than&nbsp;''C'', there is a unique index&nbsp;''i'' such that ''c''<sub>''i''</sub> is absent from ''S'', while ''c''<sub>''k''</sub>, ..., ''c''<sub>''i''+1</sub> are present in ''S'', and no other value larger than ''c''<sub>''i''</sub> is. One can therefore group those {{nowrap|''k''-combinations}} ''S'' according to the possible values 1, 2, ..., ''k'' of ''i'', and count each group separately. For a given value of ''i'' one must include
''c''<sub>''k''</sub>, ..., ''c''<sub>''i''+1</sub> in ''S'', and the remaining ''i'' elements of ''S'' must be chosen from the ''c''<sub>''i''</sub> non-negative integers strictly less than ''c''<sub>''i''</sub>; moreover any such choice will result in a {{nowrap|''k''-combinations}} ''S'' strictly less than&nbsp;''C''. The number of possible choices is <math>\tbinom{c_i}i</math>, which is therefore the number of combinations in group ''i''; the total number of ''k''-combinations strictly less than ''C'' then is
:<math>\binom{c_1}1+\binom{c_2}2+\cdots+\binom{c_k}k,</math>
and this is the index (starting from&nbsp;0) of ''C'' in the  ordered list of ''k''-combinations.

Obviously there is for every ''N''&nbsp;∈&nbsp;'''N''' exactly one ''k''-combination at index&nbsp;''N'' in the list (supposing ''k''&nbsp;≥&nbsp;1, since the list is then infinite), so the above argument proves that every ''N'' can be written in exactly one way as a sum of ''k'' binomial coefficients of the given form.

== Finding the ''k''-combination for a given number ==

The given formula allows finding the place in the lexicographic ordering of a given ''k''-combination immediately. The reverse process of finding the ''k''-combination at a given place ''N'' requires somewhat more work, but is straightforward nonetheless. By the definition of the lexicographic ordering, two ''k''-combinations that differ in their largest element ''c''<sub>''k''</sub> 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 with ''c''<sub>''k''</sub> as the largest element is <math>\tbinom{c_k}k</math>, and it has ''c''<sub>''i''</sub>&nbsp;=&nbsp;''i''&nbsp;−&nbsp;1 for all ''i''&nbsp;<&nbsp;''k'' (for this combination  all terms in the expression except <math>\tbinom{c_k}k</math> are zero). Therefore ''c''<sub>''k''</sub> is the largest number such that <math>\tbinom{c_k}k\leq N</math>. If ''k''&nbsp;&gt;&nbsp;1 the remaining elements of the ''k''-combination form the {{nowrap|''k'' − 1}}-combination corresponding to the number <math>N-\tbinom{c_k}k</math> in the combinatorial number system of degree {{nowrap|''k'' − 1}}, and can therefore be found by continuing in the same way for  <math>N-\tbinom{c_k}k</math> and {{nowrap|''k'' − 1}} instead of ''N'' and  ''k''.

=== Example ===

Suppose one wants to determine the 5-combination at position 72. The successive values of <math>\tbinom n5</math> for ''n''&nbsp;=&nbsp;4, 5, 6, ... are 0, 1, 6, 21, 56, 126, 252, ..., of which the largest one not exceeding 72 is 56, for ''n''&nbsp;=&nbsp;8. Therefore ''c''<sub>5</sub>&nbsp;=&nbsp;8, and the remaining elements form the {{nowrap|4-combination}} at position {{nowrap|72 − 56 {{=}} 16}}. The successive values of <math>\tbinom n4</math> for ''n''&nbsp;=&nbsp;3, 4, 5, ... are 0, 1, 5, 15, 35, ..., of which the largest one not exceeding 16 is 15, for ''n''&nbsp;=&nbsp;6, so ''c''<sub>4</sub>&nbsp;=&nbsp;6. Continuing similarly to search for a 3-combination at position {{nowrap|16 − 15 {{=}} 1}} one finds ''c''<sub>3</sub>&nbsp;=&nbsp;3, which uses up the final unit; this establishes <math>72=\tbinom85+\tbinom64+\tbinom33</math>, and the remaining values ''c''<sub>''i''</sub> will be the maximal ones with <math>\tbinom{c_i}i=0</math>, namely {{nowrap|''c''<sub>''i''</sub> {{=}} ''i'' − 1}}. Thus we have found the 5-combination {{nowrap|{8, 6, 3, 1, 0}}}.

== National Lottery example ==

For each of the <math>\binom{49}6</math> lottery combinations ''c''<sub>1</sub>&nbsp;<&nbsp;''c''<sub>2</sub>&nbsp;<&nbsp;''c''<sub>3</sub>&nbsp;<&nbsp;''c''<sub>4</sub>&nbsp;<&nbsp;''c''<sub>5</sub>&nbsp;<&nbsp;''c''<sub>6</sub>&nbsp;, there is a list number ''N'' between 0 and <math>\binom{49}6 - 1</math> which can be found by adding

: <math> \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. </math>

== See also ==
* [[Factorial number system]] (also called factoradics)
* [[Mixed Radix#Primorial number system|Primorial number system]]
* [[Asymmetric numeral systems]] - also e.g. of combination to natural number, widely used in data compression

== References ==
<references/>

==Further reading==
* {{Citation | ref=Reference-idHS2006 | last1=Huneke | first1=Craig | last2=Swanson | first2=Irena |author2-link= Irena Swanson | title=Integral closure of ideals, rings, and modules  | chapter-url=http://people.reed.edu/~iswanson/book/index.html | publisher=[[Cambridge University Press]] | location=Cambridge, UK | series=London Mathematical Society Lecture Note Series | isbn=978-0-521-68860-4 | mr=2266432  | year=2006 | volume=336 | chapter=Appendix 5 }}
* {{Citation | last=Caviglia | first=Giulio | title=Commutative Algebra: Geometric, Homological, Combinatorial and Computational Aspects | chapter-url=https://books.google.com/books?id=Z0RfAU2Vw6YC&pg=PA2 | publisher=[[CRC Press]] | isbn=978-1-420-02832-4 | year=2005 | chapter=A theorem of Eakin and Sathaye and Green's hyperplane restriction theorem}}
* {{Citation | last=Green | first=Mark | title=Algebraic Curves and Projective Geometry | series=Lecture Notes in Mathematics | publisher=[[Springer Publishing|Springer]] | chapter=Restrictions of linear series to hyperplanes, and some results of Macaulay and Gotzmann | doi=10.1007/BFb0085925 | isbn=978-3-540-48188-1 | year=1989| volume=1389 | pages=76–86 }}

[[Category:Combinatorics]]
[[Category:Factorial and binomial topics]]