Editing Combinatorial number system (section)

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