Combinatorial Number System - Place of A Combination in The Ordering

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 = { c_k, ..., c₂, c₁ } with c_k > ... > c₂ > c₁ as follows. From the definition of the ordering it follows that for each k-combination S strictly less than C, there is a unique index i such that c_i is absent from S, while c_k, ..., c_i+1 are present in S, and no other value larger than c_i is. One can therefore group those 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_k, ..., c_i+1 in S, and the remaining i elements of S must be chosen from the c_i non-negative integers strictly less than c_i; moreover any such choice will result in a k-combinations S strictly less than C. The number of possible choices is, which is therefore the number of combinations in group i; the total number of k-combinations strictly less than C then is

and this is the index (starting from 0) of C in the ordered list of k-combinations. Obviously there is for every N ∈ N exactly one k-combination at index N in the list (supposing k ≥ 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.