In mathematics, and in particular in combinatorics, the combinatorial number system of degree k (for some positive integer k), also referred to as combinadics, or the Macaulay representation of an integer, is a correspondence between natural numbers (taken to include0) N and k-combinations. The combinations are represented as strictly decreasing sequences ck...c2c1≥0 where each ci corresponds to the index of a chosen element in a given k-combination. Distinct numbers correspond to distinct k-combinations, and produce them in lexicographic order correspond to all of }. The correspondence does not depend on the sizen of the set that the k-combinations are taken from, so it can be interpreted as a map from N to the k-combinations taken from N; in this view the correspondence is a bijection.

The number N corresponding to (ck, ..., c2, c1) is given by

1. .

The fact that a combination corresponds to a non-negative integer was observed by Lehmer (1964). Indeed, a greedy algorithm finds the k-combination corresponding to N: take ck, then take ck−1, and so forth. Finding the number N, using the formula above, from the k-combination (ck, ..., c2, c1) is also known as "ranking", and the opposite operation (given by the greedy algorithm) as "unranking"; the operations are known by these names in most computer algebra systems, and in computational mathematics.

The term "combinatorial representation of integers" was shortened to "combinatorial number system" by Knuth (2011). He also references Ernesto Pascal (1887). The term "combinadic" is introduced by James McCaffrey.

Unlike the factorial number system, the combinatorial number system of degree k is not a mixed radix of the number N represented by a "digit" ci is not obtained from it by simply multiplying by a place value.

The main application of the combinatorial number system is that it allows rapid computation of the k-combination that is at a given position in the lexicographic ordering, without having to explicitly list the preceding it; this allows for instance random generation of k-combinations of a given set. Enumeration of k-combinations has many applications, among which are software testing, sampling, quality control, and the analysis of lottery games.

Ordering combinations

A k-combination of a set S is a subset of S with k possible k-combinations of a set S of n elements. Choosing, for any n, } 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 representsC. 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 } are less than those representing k-combinations not contained in }, 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 part9, but the next largest part6 of C is less than the next largest part7 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={c1, ..., ck} describes the number

(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 10010110012=60110 and 10100010112=65110, 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) .

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={ck, ..., c2, c1} with ck... c2 c1 as follows.

From the definition of the ordering it follows that for each k-combination S strictly less thanC, there is a unique indexi such that ci is absent from S, while ck, ..., ci+1 are present in S, and no other value larger than ci is. One can therefore group those 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 ck, ..., ci+1 in S, and the remaining i elements of S must be chosen from the ci non-negative integers strictly less than ci; moreover any such choice will result in a S strictly less thanC, 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 from0) of C in the ordered list of k-combinations.

Obviously there is for every N∈N exactly one k-combination at indexN 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 ck 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 ck, and it has ci=i−1 for all i<k are zero). Therefore ck. If k1 the remaining elements of the k-combination form the in the combinatorial number system of degree and instead of N and k.

Example

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 c5=8, and the remaining elements form the at position 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 c4=6. Continuing similarly to search for a 3-combination at position one finds c3=, and the remaining values ci, namely . Thus we have found the 5-combination }.

National Lottery example

lottery combinations c1<c2<c3<c4<c5<c6, there is a list number N which can be found by adding

See also

• Factorial number system (also called factoradics)

• Primorial number system

• Asymmetric numeral systems - also e.g. of combination to natural number, widely used in data compression

References

Further reading