In mathematics, a combinadic is an ordered integer partition, or composition. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Number theory, a partition of a positive Integer n is a way of writing n as a Sum of positive integers In Mathematics, a composition of a positive Integer n is a way of writing n as a Sum of Positive integers Two sums which Combinadics provide a lexicographical index for combinations. The pursuit of lexicography is divided into two related disciplines Practical lexicography is the art or Craft of compiling writing and editing dictionaries The word index is used in variety of senses in Mathematics. In perhaps the most frequent sense an index is a Superscript In combinatorial mathematics, a combination is an un-ordered collection of distinct elements usually of a prescribed size and taken from a given set Applications for combinadics include software testing, sampling, quality control, and the analysis of gambling games such as Canada's national 6/49 lottery. Software testing is an Empirical investigation conducted to provide stakeholders with information about the quality of the product or service under test, with respect to the Sampling is that part of Statistical practice concerned with the selection of individual observations intended to yield some knowledge about a population of concern In Engineering and Manufacturing, quality control and quality engineering are involved in developing systems to ensure products or services Lotto 6/49 is one of Canada 's national Lottery games along with Lotto Super 7.
For definiteness, we will consider the k-combinations on the set S = {0, 1, . In combinatorial mathematics, a combination is an un-ordered collection of distinct elements usually of a prescribed size and taken from a given set . . , 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, . In Mathematics and related technical fields the term map or mapping is often a Synonym for function. . . , 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 ith k-combination taken from the set of n elements. In Mathematics, abuse of notation occurs when an author uses a Mathematical notation in a way that is not formally correct but that seems likely to simplify the exposition Then the index for the ten 3-combinations of the set of five elements {0, 1, 2, 3, 4} can be written out as follows.
ith 3-combination
Index i C(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 ith 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. In Computer programming and some branches of Mathematics, a string is an ordered Sequence of Symbols. 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 ith combinadic in this system is defined to be the ordered n-tuple consisting of the letter positions for the 1s in the nth word in lexicographical order, reading from left to right. In Mathematics, a tuple is a Sequence (also known as an "ordered list" of values called the components of the tuple In Mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order or lexicographic(al product
We can now write out the combinadics for the ten 3-combinations of the set of five elements in the following table.
ith word
(places) ith combinadic
Index i (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. For the American actor see James McCaffrey. James D McCaffrey is a software engineer and author known for his contributions to the fields of mathematical combinatorics
The more useful composition-based definition for a combinadic can be illustrated using an example. In Mathematics, a composition of a positive Integer n is a way of writing n as a Sum of Positive integers Two sums which 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.
R ith word
e Index Breakdown of Index (places) ith combinadic
f i (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 ith combinadic M(n,k)(i) is the unique strictly decreasing sequence (mk−1, mk−2, . In Mathematics, a sequence is an ordered list of objects (or events . . , m0) of k integers lying between n − 1 and 0 so that C(mk−1,k) + C(mk−2,k − 1) + . . . + C(m0,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 mk−1 so that C(mk−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(mk−1,k), n is set to the previous mk−1, and k is reduced by one. This is continued until k is reduced to zero. As McCaffrey points out in his MSDN article, efficiently finding the largest mk−1 is the key to calculating a k-combination from its index value (see his discussion of the helper function LargestV()). In combinatorial mathematics, a combination is an un-ordered collection of distinct elements usually of a prescribed size and taken from a given set The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function
Combinadics, unlike factoradics, does not appear to be a numeral system, although it has very much the look and feel of one. In Combinatorics, factoradic is a specially constructed number system A numeral system (or system of numeration) is a Mathematical notation for representing numbers of a given set by symbols in a consistent manner Look and feel is a term used in descriptions of products and fields such as Marketing, Branding and Trademarking to signify the experience a person has using In particular, it is different from a mixed radix system. Mixed radix Numeral systems are Non-standard positional numeral systems in which the numerical base varies from position to position
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. In Mathematics, a theorem is a statement proven on the basis of previously accepted or established statements In Mathematics, a number system is a set of Numbers (in the broadest sense of the word together with one or more operations such as Addition
- A simple implementation of combinadics in Java by Michael J. Hudson
See also
In Combinatorics, factoradic is a specially constructed number systemDapyx Software network: MP3 Explorer | Ebook Manager | Zenithic