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 ck > ... > c2 > c1 ≥ 0 where each ci corresponds to the index of a chosen element in a given k-combination.
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 (ck, ..., c2, c1) is given by The fact that a unique sequence corresponds to any non-negative number N was first observed by D. H.
[1] Indeed, a greedy algorithm finds the k-combination corresponding to N: take ck maximal with
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.
[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;[5] the term "combinadic" is introduced by James McCaffrey[6] (without reference to previous terminology or work).
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 k-combinations 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.
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
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.
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.
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.
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 ci is absent from S, while ck, ..., ci+1 are present in S, and no other value larger than ci is.
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 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.
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 as the largest element is
, and it has ci = i − 1 for all i < k (for this combination all terms in the expression except
If k > 1 the remaining elements of the k-combination form the k − 1-combination corresponding to the number
in the combinatorial number system of degree k − 1, and can therefore be found by continuing in the same way for
Therefore c5 = 8, and the remaining elements form the 4-combination at position 72 − 56 = 16.
Continuing similarly to search for a 3-combination at position 16 − 15 = 1 one finds c3 = 3, which uses up the final unit; this establishes
, and the remaining values ci will be the maximal ones with
lottery combinations c1 < c2 < c3 < c4 < c5 < c6 , there is a list number N between 0 and