In mathematics, and in particular in combinatorics, the combinatorial number system of degree k (for some positive integer k), also referred to as combinadics, is a correspondence between natural numbers (taken to include 0) N and k-combinations, represented as strictly decreasing sequences ck > ... > c2 > c1 ≥ 0. Since the latter are strings of numbers, one can view this as a kind of numeral system for representing N, although the main utility is representing a k-combination by N rather than the other way around. Distinct numbers correspond to distinct k-combinations, and produce them in lexicographic order; moreover the numbers less than 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 (ck,...,c2,c1) is given by
The fact that a unique sequence so corresponds to any number N was observed by D.H. Lehmer. Indeed a greedy algorithm finds the k-combination corresponding to N: take ck maximal with, then take ck − 1 maximal with, and so forth. The originally used term "combinatorial representation of integers" is shortened to "combinatorial number system" by Knuth, who also gives a much older reference; the term "combinadic" is introduced by James McCaffrey with a computer program implementation.
Unlike the factorial number system, the combinatorial number system of degree k is not a mixed radix system: the part 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 software testing, sampling, quality control, and the analysis of lottery games.
This is also known as "rank" ("ranking" and "unranking"), and is known by that name in most CAS software and in computational mathematics.
Read more about Combinatorial Number System: Ordering Combinations, Place of A Combination in The Ordering, Finding The k-combination For A Given Number, Applications
Famous quotes containing the words number and/or system:
“Not too many years ago, a child’s experience was limited by how far he or she could ride a bicycle or by the physical boundaries that parents set. Today ... the real boundaries of a child’s life are set more by the number of available cable channels and videotapes, by the simulated reality of videogames, by the number of megabytes of memory in the home computer. Now kids can go anywhere, as long as they stay inside the electronic bubble.”
—Richard Louv (20th century)
“To care for the quarrels of the past, to identify oneself passionately with a cause that became, politically speaking, a losing cause with the birth of the modern world, is to experience a kind of straining against reality, a rebellious nonconformity that, again, is rare in America, where children are instructed in the virtues of the system they live under, as though history had achieved a happy ending in American civics.”
—Mary McCarthy (1912–1989)