Combinatorial number system

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 ${\displaystyle {\tbinom {n}{k}}}$ correspond to all k-combinations of {0, 1, ..., n − 1}. 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

${\displaystyle N={\binom {c_{k}}{k}}+\cdots +{\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 ${\displaystyle {\tbinom {c_{k}}{k}}\leq N}$, then take c_k−1 maximal with ${\displaystyle {\tbinom {c_{k-1}}{k-1}}\leq N-{\tbinom {c_{k}}{k}}}$, 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;^[5] the term "combinadic" is introduced by James McCaffrey^[6] (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 ${\displaystyle {\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 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.