# Lottery Information

## Combinadic

In mathematics, a combinadic is an ordered integer partition, or composition. Combinadics provide a lexicographical index for combinations. Applications for combinadics include software testing, sampling, quality control, and the analysis of gambling games such as Canada's national 6/49 lottery.

For definiteness, we will consider the *k*-combinations on the set *S* = {0, 1, ..., *n* − 1} of the first *n* integers starting from 0. Recall that there are C(*n*,*k*) = *n*! / ( *k*! (*n* − *k*)! ) of these. The index we are looking for is the mapping associating the numbers *i* = 0, 1, ..., C(*n*,*k*) − 1 with the list of *k*-combinations having their elements written in ascending order, and themselves ordered lexicographically. By abuse of notation we denote as C_{(n,k)}(*i*) the *i*^{th} *k*-combination taken from the set of *n* elements. Then the index for the ten 3-combinations of the set of five elements can be written out as follows.

i^{th}3-combination IndexiC_{(5,3)}(i) 0 {0, 1, 2} 1 {0, 1, 3} 2 {0, 1, 4} 3 {0, 2, 3} 4 {0, 2, 4} 5 {0, 3, 4} 6 {1, 2, 3} 7 {1, 2, 4} 8 {1, 3, 4} 9 {2, 3, 4}

The definition we want for an *i*^{th} combinadic M_{(n,k)}(*i*) on the C(*n*,*k*) *k*-combinations of the set of *n* elements is most directly achieved by first considering the list of all possible words *n* letters long consisting of *k* 1s and *n* − *k* 0s. We designate the letter positions, or places, in the word as *n* − 1, *n* − 2, ..., 1, 0 in descending order, lowest letter position on the right. Then the *i*^{th} combinadic in this system is defined to be the ordered *n*-tuple consisting of the letter positions for the 1s in the *n*^{th} word in lexicographical order, reading from left to right.

We can now write out the combinadics for the ten 3-combinations of the set of five elements in the following table.

i^{th}word (places)i^{th}combinadic Indexi(43210) M_{(5,3)}(i) ||||| 0 00111 (2, 1, 0) 1 01011 (3, 1, 0) 2 01101 (3, 2, 0) 3 01110 (3, 2, 1) 4 10011 (4, 1, 0) 5 10101 (4, 2, 0) 6 10110 (4, 2, 1) 7 11001 (4, 3, 0) 8 11010 (4, 3, 1) 9 11100 (4, 3, 2)

Clearly the combinadics also list all the *k*-combinations from the set of *n* elements in lexicographical order, but here the elements are listed in *decreasing*, not increasing order. In this MSDN article, James D. McCaffrey shows that the conventional combinations index is easily obtained from the combinadics.

The more useful composition-based
definition for a combinadic can be illustrated using an example.
Consider the combinadic with index 72 in the system of 5-combinations
from the set of 10 elements. This is M_{(10,5)}(72) = (8, 6, 3,
1, 0). By studying the seventy-three words consisting of five 1s and
five 0s that lead up to this combinadic, it becomes clear that there is
a simple relationship between the numbers in the combinadic code and an
ordered partition of the index number.

Ri^{th}word e Index Breakdown of Index (places)i^{th}combinadic fi(9876543210) M_{(10,5)}(i) |||||||||| A) 0 0000011111 (4,3,2,1,0) 1 0000101111 (5,3,2,1,0) 2 0000110111 (5,4,2,1,0) 3 0000111011 (5,4,3,1,0) 4 0000111101 (5,4,3,2,0) 5 0000111110 (5,4,3,2,1) 6 0001001111 (6,3,2,1,0) 7 0001010111 (6,4,2,1,0) ... ... ... ... 53 0011110010 (7,6,5,4,1) 54 0011110100 (7,6,5,4,2) B) 55 C(8,5) − 1 0011111000 (7,6,5,4,3) C) 56 C(8,5) 0100001111 (8,3,2,1,0) ^ ^ 57 0100010111 (8,4,2,1,0) 58 0100011011 (8,4,3,1,0) 59 0100011101 (8,4,3,2,0) 60 0100011110 (8,4,3,2,1) 61 0100100111 (8,5,2,1,0) ... ... ... ... 67 0100110110 (8,5,4,2,1) 68 0100111001 (8,5,4,3,0) 69 0100111010 (8,5,4,3,1) D) 70 C(8,5) + C(6,4) − 1 0100111100 (8,5,4,3,2) E) 71 C(8,5) + C(6,4) 0101000111 (8,6,2,1,0) ^ ^ ^ ^ F) 72 C(8,5) + C(6,4) + C(3,3) + C(1,2) + C(0,1) 0101001011 (8,6,3,1,0) ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

Notice first of all that between reference A and reference B, the five 1s run through all the possible patterns among the eight rightmost places 0, 1, 2, ..., 7 in the word. There are C(8, 5) = 56 of these, so since reference A is at index 0, reference B has to be at index C(8,5) − 1 = 55. At the next index, reference C, the leftmost 1 achieves its final resting place of position 8 on index C(8,5) = 56, while the remaining four 1s are reset to the far right of the word. Next notice that between reference C and reference D, the remaining four 1s run through all the possible patterns in the six rightmost places 0, 1, 2, ..., 5 in the word. There are C(6,4) = 15 of these, so reference D lies at index C(8,5) + C(6,4) − 1 = 70, and the next index, reference E, where the second leftmost 1 achieves its final resting place of position 6 and the remaining three 1s are reset to the right, is index C(8,5) + C(6,4) = 71. The three rightmost 1s run through the single (C(3,3) = 1) pattern on the three rightmost places before the third rightmost 1 takes up its final station at place 3 at reference F. The two rightmost 1s run through no (C(1,2) = 0) patterns before the second rightmost 1 doesn't move; similarly the one rightmost 1 runs through no (C(0,1) = 0) patterns before it doesn't move.

The relationship between combinadics and ordered integer partitions is formalized in the following.

- Definition
- (after McCaffrey)
- combinadic
- In the context of the system of
*C*(*n*,*k*)*k*-combinations on the set of*n*objects, and for each non-negative integer*i*less than C(*n*,*k*), the*i*^{th}combinadic*M*_{(n,k)}(*i*) is the unique strictly decreasing sequence (*m*_{k−1},*m*_{k−2}, ...,*m*_{0}) of*k*integers lying between*n*− 1 and 0 so that*C*(m_{k−1},*k*) +*C*(*m*_{k−2},*k*− 1) + ... +*C*(*m*_{0},1) =*i*.

Clearly the index value *i* for any combinadic can be immediately calculated from its elements.

To get the elements of the combinadic *M*_{(n,k)}(*i*) from its index *i*, we first find the largest first element *m*_{k−1} so that C(m_{k−1}, *k*) is less than or equal to *i*. The second element is found by repeating the procedure in the reduced combinadic system where *i* is reduced by the previous C(m_{k−1},*k*), *n* is set to the previous m_{k−1}, and *k* is reduced by one. This is continued until *k* is reduced to zero. As McCaffrey points out in his MSN article, efficiently finding the largest *m*_{k−1} is the key to calculating a *k*-combination from its index value (see his discussion of the helper function **LargestV()**).

Combinadics, unlike factoradics, does not appear to be a numeral system, although it has very much the look and feel of one. In particular, it is different from a mixed radix system.

### External links

- "Generating the mth Lexicographical Element of a Mathematical Combination", by James McCaffrey. Volt Information Sciences, Inc. July 2004 (a Visual C# .NET article from the MSDN Library) Implementation of combinadics in C# source code

- "The
Art Of Computer Programming: Pre-Fascicle 3A, A DRAFT OF SECTION
7.2.1.3: GENERATING ALL COMBINATIONS" by Donald E. Knuth (compressed
postscript file) See pp 5-6 (of 11th revision) for a short discussion. Knuth has that Derrick Lehmer published the basic theorem in 1964, and an Ernesto Pascal described a
*combinatorial number system*around 1887.