1 Answers
In mathematics, and in particular in combinatorics, the combinatorial number system of degree k , also referred to as combinadics, or the Macaulay representation of an integer, is a correspondence between natural numbers 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. 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 is given by
The fact that a unique sequence corresponds to any non-negative number N was first observed by D. H. Lehmer. Indeed, a greedy algorithm finds the k-combination corresponding to N: take ck maximal with ≤ N {\displaystyle {\tbinom {c_{k}}{k}}\leq N} , then take ck−1 maximal with ≤ N − {\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 is also known as "ranking", and the opposite operation as "unranking"; the operations are known by these names in most computer algebra systems, and in computational mathematics.
The originally used term "combinatorial representation of integers" was shortened to "combinatorial number system" by Knuth,who also gives a much older reference;the term "combinadic" is introduced by James McCaffrey.