Editing Combinatorial number system (section)

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