Combinatorial number system explained

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 include 0) N and k-combinations. The combinations are represented as strictly decreasing sequences c_k > ... > c₂ > c₁ ≥ 0 where each c_i 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. The numbers less than

\tbinom nk correspond to all of . The correspondence does not depend on the size n 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 (c_k, ..., c₂, c₁) is given by

N = \binom{c _{k}k+ … +\binom{c} _{2}2+\binom{c} _{1}1} .

The fact that a unique sequence corresponds to any non-negative number N was first observed by D. H. Lehmer.^[1] Indeed, a greedy algorithm finds the k-combination corresponding to N: take c_k maximal with

\tbinom{c _{k}k\leq} N , then take c_k−1 maximal with \tbinom{c _{k-1} }\leq N - \tbinomk, and so forth. Finding the number N, using the formula above, from the k-combination (c_k, ..., c₂, c₁) 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.^{[2] [3]}

The originally used term "combinatorial representation of integers" was shortened to "combinatorial number system" by Knuth,^[4] who also gives a much older reference;the term "combinadic" is introduced by James McCaffrey (without reference to previous terminology or work).

Unlike the factorial number system, the combinatorial number system of degree k is not a mixed radix system: the part

\tbinom{c _{i}i} of the number N represented by a "digit" c_i 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 (distinct) elements. The main purpose of the combinatorial number system is to provide a representation, each by a single number, of all

\tbinom nk 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 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 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 =  and C′ = , 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 =  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) .

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 =  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 S according to the possible values 1, 2, ..., k of i, and count each group separately. For a given value of i one must includec_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 S strictly less than C. The number of possible choices is

\tbinom{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\binom{c _{1}1+\binom{c} _{2}2+ … +\binom{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 the largest element is

\tbinom{c _{k}k} , and it has c_i = i − 1 for all i < k (for this combination all terms in the expression except \tbinom{c _{k}k} are zero). Therefore c_k is the largest number such that \tbinom{c _{k}k\leq} N . If k > 1 the remaining elements of the k-combination form the -combination corresponding to the number N - \tbinom{c _{k}k} in the combinatorial number system of degree, and can therefore be found by continuing in the same way for N - \tbinom{c _{k}k} and instead of N and k.

Example

Suppose one wants to determine the 5-combination at position 72. The successive values of

\tbinom 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 at position . The successive values of \tbinom 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 one finds c₃ = 3, which uses up the final unit; this establishes 72= \tbinom 85+ \tbinom 64+ \tbinom 33 , and the remaining values c_i will be the maximal ones with \tbinom{c _{i}i=0} , namely . Thus we have found the 5-combination .

National Lottery example

For each of the

\binom{ 49 } 6 lottery combinations c₁ < c₂ < c₃ < c₄ < c₅ < c₆ , there is a list number N between 0 and \binom{ 49 } 6 - 1 which can be found by adding\binom{ 49- c _{1}} 6 + \binom{ 49- c _{2}} 5 + \binom{ 49- c _{3}} 4 + \binom{ 49- c _{4}} 3 + \binom{ 49- c _{5}} 2 + \binom{ 49- c _{6}} 1 .

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

1. Applied Combinatorial Mathematics, Ed. E. F. Beckenbach (1964), pp.27−30.
2. http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf Generating Elementary Combinatorial Objects
3. Web site: Combinations — Sage 9.4 Reference Manual: Combinatorics.
4. .