Editing Combinatorial number system (section)

== 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}}.