Combinatorial number system

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 ( n k ) possible k-combinations of a set S of n elements. Choosing, for any n, {0, 1, ..., n − 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 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 {0, 1, ..., n − 1} are less than those representing k-combinations not contained in {0, 1, ..., n − 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 ordering of the decreasing sequence of their elements. So comparing the 5-combinations C = {0,3,4,6,9} and C' = {0,1,3,7,9}, one has that C comes before C', since they have the same largest part 9, but the next largest part 6 of C is less than the next largest part 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 = {c₁,...,c_k} describes the number

2 c 1 + 2 c 2 + ⋯ + 2 c k

(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₂ = 601₁₀ and 1010001011₂ = 651₁₀, 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) 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 = { 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 ( c i i ) , which is therefore the number of combinations in group i; the total number of k-combinations strictly less than C then is

( c 1 1 ) + ( c 2 2 ) + ⋯ + ( c k k ) ,

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.

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_k 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_k as largest element is ( c k k ) , and it has c_i = i − 1 for all i < k (for this combination all terms in the expression except ( c k k ) are zero). Therefore c_k is the largest number such that ( c k k ) ≤ N . If k > 1 the remaining elements of the k-combination form the k − 1-combination corresponding to the number N − ( c k k ) in the combinatorial number system of degree k − 1, and can therefore be found by continuing in the same way for N − ( c k k ) and k − 1 instead of N and k.

Example

Suppose one wants to determine the 5-combination at position 72. The successive values of ( n 5 ) for n = 4, 5, 6, ... are 0, 1, 6, 21, 56, 126, 252, ..., of which the largest one not exceeding 72 is 56, for n = 8. Therefore c₅ = 8, and the remaining elements form the 4-combination at position 72 − 56 = 16. The successive values of ( n 4 ) for n = 3, 4, 5, ... are 0, 1, 5, 15, 35, ..., of which the largest one not exceeding 16 is 15, for n = 6, so c₄ = 6. Continuing similarly to search for a 3-combination at position 16 − 15 = 1 one finds c₃ = 3, which uses up the final unit; this establishes 72 = ( 8 5 ) + ( 6 4 ) + ( 3 3 ) , and the remaining values c_i will be the maximal ones with ( c i i ) = 0 , namely c_i = i − 1. Thus we have found the 5-combination {8, 6, 3, 1, 0}.

National Lottery example in Excel

For each of the ( 49 6 ) lottery combinations c₁ < c₂ < c₃ < c₄ < c₅ < c₆ < , there is a list number N between 0 and ( 49 6 ) − 1 which can be found by adding

( 49 − c 1 6 ) + ( 49 − c 2 5 ) + ( 49 − c 3 4 ) + ( 49 − c 4 3 ) + ( 49 − c 5 2 ) + ( 49 − c 6 1 ) .

Suppose you want to find a position of a British National Lottery result 3,6,15,17,18,35 in a list of possible results. Excel function COMBIN(49,6) would show that number of results is 13983816. Now if you put numbers 3,6,15,17,18,35 each in its cell and formulas COMBIN(49-3,6), COMBIN(49-6,5), COMBIN(49-15,4), COMBIN(49-17,3), COMBIN(49-18,2), 49−35 under each of them. Use cell references instead of actual values, the actual values are provided for readability. You would get a row of numbers of 9366819,962598,46376,4960,465,14. Adding these would show particular position 10381232. Note that you do not need use formula COMBIN(49-35,1) to get 14. You can have it by subtraction 49-35 alone. Also the COMBIN function does not return 0 in case 49-X becomes less than 6. You'd need to use IF with ISNUMBER function to convert #NUM! into 0.

Now the reverse engineering is a bit trickier. You could use 49 IF statements in one cell or use solver to find maximum argument for COMBIN result to be less or equal than position number. Instead let's use a table of 6 by 49 and use MATCH function where resulting row number would be the argument and a ball number. If you make column headings from 6 to 1 (B1:G1) in descending order and row labels of 1 to 49 (A2:A50) in ascending order (vertically ascending in Excel means numbers growing from top to bottom). Then if you fill up the table with formula COMBIN($A2,B$1) starting from left top corner. $ signs will make sure that index values are always taken from heading row and label column. Replace #NUM! with zeros. You should get something like this:

6 5 4 3 2 11 0 0 0 0 0 12 0 0 0 0 1 23 0 0 0 1 3 34 0 0 1 4 6 45 0 1 5 10 10 56 1 6 15 20 15 67 7 21 35 35 21 78 28 56 70 56 28 89 84 126 126 84 36 910 210 252 210 120 45 1011 462 462 330 165 55 1112 924 792 495 220 66 12...49 13983816 1906884 211876 18424 1176 49

Now if you create a new row of six cells and fill them with formulas which would find the largest values in each column which are less than or equal to position number in question: The first cell with =INDEX(B2:B50,MATCH(10381232,B2:B50)), the rest of the cells with

INDEX(C2:C50,MATCH(10381232-SUM(of previous cells),C2:C50))...INDEX(G2:G50,MATCH(10381232-SUM(of previous cells),G2:G50))

This would present you with a row of values you have already seen 9366819,962598,46376,4960,465,14 Now in a next row first cell write =49-MATCH(10381232,B2:B50) and similarly

=49-MATCH(10381232-9366819,C2:C50)...=49-MATCH(10381232-9366819-962598-46376-4960-465,G2:G50)

Again use the references to cells instead of actual values. You should be presented with original ball numbers of 3,6,15,17,18,35.

Now you can generate a fresh Lottery number combination from single =randbetween(1,combin(49,6)) or you could look at the list position numbers of earlier results to see if there is a trend.

Applications

One could use the combinatorial number system to list or traverse all k-combinations of a given finite set, but this is a very inefficient way to do that. Indeed, given some k-combination it is much easier to find the next combination in lexicographic ordering directly than to convert a number to a k-combination by the method indicated above. To find the next combination, find the smallest i ≥ 2 for which c_i ≥ c_i−1+2 (if there is no such i, take i = k+1); then increase c_i−1 by one and set all c_j with j < i − 1 to their minimal value j − 1. If the k-combination is represented by its characteristic vector, that is as a binary value with k bits 1, then the next such value can be computed without any loop using bitwise arithmetic: the following C++function will advance x to that value or return false:

This is called Gosper's hack; corresponding assembly code was described as item 175 in HAKMEM.

On the other hand the possibility to directly generate the k-combination at index N has useful applications. Notably, it allows generating a random k-combination of an n-element set using a random integer N with 0 ≤ N < ( n k ) , simply by converting that number to the corresponding k-combination. If a computer program needs to maintain a table with information about every k-combination of a given finite set, the computation of the index N associated with a combination will allow the table to be accessed without searching.