Combinatorial number system

Inmathematics,and in particular incombinatorics,thecombinatorial number systemof degreek(for some positiveintegerk), also referred to ascombinadics,or theMacaulay representation of an integer,is a correspondence betweennatural numbers(taken to include 0)Nandk-combinations.The combinations are represented asstrictly decreasing sequencesc_k>... >c₂>c₁≥ 0 where eachc_icorresponds to the index of a chosen element in a givenk-combination. Distinct numbers correspond to distinctk-combinations, and produce them inlexicographic order.The numbers less than ${\tbinom {n}{k}}$ correspond to allk-combinationsof{0, 1,...,n− 1}. The correspondence does not depend on the sizenof the set that thek-combinations are taken from, so it can be interpreted as a map fromNto thek-combinations taken fromN;in this view the correspondence is abijection.

The numberNcorresponding to (c_k,...,c₂,c₁) is given by

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 numberNwas first observed byD. H. Lehmer.^[1]Indeed, agreedy algorithmfinds thek-combination corresponding toN:takec_kmaximal with ${\tbinom {c_{k}}{k}}\leq N$ ,then takec_k−1maximal with ${\tbinom {c_{k-1}}{k-1}}\leq N-{\tbinom {c_{k}}{k}}$ ,and so forth. Finding the numberN,using the formula above, from thek-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 mostcomputer algebra systems,and incomputational mathematics.^[2]^[3]

The originally used term "combinatorial representation of integers" was shortened to "combinatorial number system" byKnuth,^[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 thefactorial number system,the combinatorial number system of degreekis not amixed radixsystem: the part ${\tbinom {c_{i}}{i}}$ of the numberNrepresented by a "digit"c_iis 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 thek-combination that is at a given position in the lexicographic ordering, without having to explicitly list thek-combinationspreceding it; this allows for instance random generation ofk-combinations of a given set.Enumeration ofk-combinationshas many applications, among which aresoftware testing,sampling,quality control,and the analysis oflotterygames.

Ordering combinations

Ak-combination of a setSis asubsetofSwithk(distinct) elements. The main purpose of the combinatorial number system is to provide a representation, each by a single number, of all ${\tbinom {n}{k}}$ possiblek-combinations of a setSofnelements. Choosing, for anyn,{0, 1,...,n− 1} as such a set, it can be arranged that the representation of a givenk-combinationCis independent of the value ofn(althoughnmust of course be sufficiently large); in other words consideringCas a subset of a larger set by increasingnwill not change the number that representsC.Thus for the combinatorial number system one just considersCas ak-combination of the setNof all natural numbers, without explicitly mentioningn.

In order to ensure that the numbers representing thek-combinations of{0, 1,...,n− 1} are less than those representingk-combinations not contained in{0, 1,...,n− 1}, thek-combinations must be ordered in such a way that their largest elements are compared first. The most natural ordering that has this property islexicographic orderingof thedecreasingsequence of their elements. So comparing the 5-combinationsC= {0,3,4,6,9} andC′ = {0,1,3,7,9}, one has thatCcomes beforeC′, since they have the same largest part 9, but the next largest part 6 ofCis less than the next largest part 7 ofC′; 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 thekraised bits in thebinary representationof a number, so thatC= {c₁,...,c_k} describes the number

2^{c_{1}}+2^{c_{2}}+\cdots +2^{c_{k}}

(this associates distinct numbers toallfinite sets of natural numbers); then comparison ofk-combinations can be done by comparing the associated binary numbers. In the exampleCandC′ correspond to numbers 1001011001₂= 601₁₀and 1010001011₂= 651₁₀,which again shows thatCcomes beforeC′. This number is not however the one one wants to represent thek-combination with, since many binary numbers have a number of raised bits different fromk;one wants to find the relative position ofCin the ordered list of (only)k-combinations.

Place of a combination in the ordering

The number associated in the combinatorial number system of degreekto ak-combinationCis the number ofk-combinations strictly less thanCin the given ordering. This number can be computed fromC= {c_k,...,c₂,c₁} withc_k>... >c₂>c₁as follows.

From the definition of the ordering it follows that for eachk-combinationSstrictly less thanC,there is a unique indexisuch thatc_iis absent fromS,whilec_k,...,c_i+1are present inS,and no other value larger thanc_iis. One can therefore group thosek-combinationsSaccording to the possible values 1, 2,...,kofi,and count each group separately. For a given value ofione must include c_k,...,c_i+1inS,and the remainingielements ofSmust be chosen from thec_inon-negative integers strictly less thanc_i;moreover any such choice will result in ak-combinationsSstrictly less thanC.The number of possible choices is ${\tbinom {c_{i}}{i}}$ ,which is therefore the number of combinations in groupi;the total number ofk-combinations strictly less thanCthen is

{\binom {c_{1}}{1}}+{\binom {c_{2}}{2}}+\cdots +{\binom {c_{k}}{k}},

and this is the index (starting from 0) ofCin the ordered list ofk-combinations.

Obviously there is for everyN∈Nexactly onek-combination at indexNin the list (supposingk≥ 1, since the list is then infinite), so the above argument proves that everyNcan be written in exactly one way as a sum ofkbinomial coefficients of the given form.

Finding thek-combination for a given number

The given formula allows finding the place in the lexicographic ordering of a givenk-combination immediately. The reverse process of finding thek-combination at a given placeNrequires somewhat more work, but is straightforward nonetheless. By the definition of the lexicographic ordering, twok-combinations that differ in their largest elementc_kwill 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 withc_kas the largest element is ${\tbinom {c_{k}}{k}}$ ,and it hasc_i=i− 1 for alli<k(for this combination all terms in the expression except ${\tbinom {c_{k}}{k}}$ are zero). Thereforec_kis the largest number such that ${\tbinom {c_{k}}{k}}\leq N$ .Ifk> 1 the remaining elements of thek-combination form thek− 1-combination corresponding to the number $N-{\tbinom {c_{k}}{k}}$ in the combinatorial number system of degreek− 1,and can therefore be found by continuing in the same way for $N-{\tbinom {c_{k}}{k}}$ andk− 1instead ofNandk.

Example

Suppose one wants to determine the 5-combination at position 72. The successive values of ${\tbinom {n}{5}}$ forn= 4, 5, 6,... are 0, 1, 6, 21, 56, 126, 252,..., of which the largest one not exceeding 72 is 56, forn= 8. Thereforec₅= 8, and the remaining elements form the4-combinationat position72 − 56 = 16.The successive values of ${\tbinom {n}{4}}$ forn= 3, 4, 5,... are 0, 1, 5, 15, 35,..., of which the largest one not exceeding 16 is 15, forn= 6, soc₄= 6. Continuing similarly to search for a 3-combination at position16 − 15 = 1one findsc₃= 3, which uses up the final unit; this establishes $72={\tbinom {8}{5}}+{\tbinom {6}{4}}+{\tbinom {3}{3}}$ ,and the remaining valuesc_iwill be the maximal ones with ${\tbinom {c_{i}}{i}}=0$ ,namelyc_i=i− 1.Thus we have found the 5-combination{8, 6, 3, 1, 0}.

National Lottery example

For each of the ${\binom {49}{6}}$ lottery combinationsc₁<c₂<c₃<c₄<c₅<c₆,there is a list numberNbetween 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}}.

References

^Applied Combinatorial Mathematics,Ed. E. F. Beckenbach (1964), pp.27−30.
^Generating Elementary Combinatorial Objects,Lucia Moura, U. Ottawa, Fall 2009
^"Combinations — Sage 9.4 Reference Manual: Combinatorics".
^Knuth, D. E.(2005), "Generating All Combinations and Partitions",The Art of Computer Programming,vol. 4, Fascicle 3, Addison-Wesley, pp. 5−6,ISBN 0-201-85394-9.
^Pascal, Ernesto (1887),Giornale di Matematiche,vol. 25, pp. 45−49
^McCaffrey, James(2004),Generating the mth Lexicographical Element of a Mathematical Combination,Microsoft Developer Network