- Combinádico
-
Combinádico (o número secuencial combinatório) es en matematicas una partición ordenada, o una composición. Los números secuenciales combinatorios proporcionan un índice orden lexicográfico de las combinaciones. Los combinádicos se pueden usar en pruebas de software, muestreo estadístico, control de calidad y análisis de juegos de azar.
Por definición, consideramos que k-combinaciones del conjunto S = {0,1,..., n − 1} de los primeros n enteros empezando por 0. Hay C(n,k) = n! / ( k! (n − k)! ) posibles combinaciones. El índice a buscar es el asociado a los números i = 0, 1,..., C(n,k) − 1 con los elementos de las k-combinaciones ordenados en orden ascendente y a sí mismas ordenadas lexicográficamente.El índice para las diez 3-combinaciones del conjunto de cinco elementos {1, 2, 3, 4, 5} se puede escribir de la siguiente manera:
iésimo 3-combinación Índice 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}La definición que queremos para un iésimo combinádico M(n,k)(i) de entre las C(n,k) k-combinaciones del conjunto de n elementos se puede lograr más fácilmente si primero consideramos la lista de todas las posibles palabras de n letras consistentes en k 1s y n − k 0s. Designamos las posiciones de las letras, o lugares, en la palabra como n − 1, n − 2,..., 1, 0 en orden descendente, con la posición más baja a la derecha. Entonces el iésimo combinádico en ese sistema se define como la tupla consistente en las posiciones para los 1s en la iésima palabra en orden lexicográfico, leyendo de izquierda a derecha.
Podemos listar ahora los combinádicos para las diez 3-combinaciones del conjunto de cinco elementos en la siguiente tabla.
iésima palabra (lugares) iésimo combinádico Índice 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)Claramente los combinádicos también listan todas las k-combinaciones del conjunto de n elementos en orden lexicográfico, pero en este caso los elementos están listados en orden descendente, no ascendente. En este artículo de MSDN, James D. McCaffrey muestra que el índice convencional de combinaciones se puede obtener fácilmente usando combinádicos.
La manera más útil de definir un combinádico se puede ilustrar con un ejemplo. Considerando el combinádico con índice 72 en el sistema de 5-combinaciones del conjunto de 10 elementos. Este es el M(10,5)(72) = (8, 6, 3, 1, 0). Estudiando las 27 palabras consistentes en cinco 1s y cinco 0s que conforman este combinádico, está claro que existe una simple relación entre los números en el código combinádico y la partición ordenada del índice numérico
R iésima palabra e Índice Descomposición (lugares) iésimo combinádico 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) ^ ^ ^ ^ ^ ^ ^ ^ ^ ^Nótese primero que todo lo que está entre la referencia A y la referencia B, los cinco primeros 1s toman todos los posibles valores en las posiciones de más a la derecha 0, 1, 2,..., 7 de la palabra. Hay C(8, 5) = 56, por lo que estando la referencia A en el índice 0, la referencia B tiene que estar en el índice C(8,5) − 1 = 55. En el siguiente índice, la referencia C, el 1 de más a la izquierda toma como posición final 8 en el índice C(8,5) = 56, mientras que los restantes cuatro 1s son restituidos en la parte más a la derecha de la palabra. Nótese después que entre la referencia C y la referencia D, los restantes cuatro 1s toman todos los posibles valores de las seis posiciones 0, 1, 2,..., 5 de más a la derecha. Hay C(6,4) = 15, así que la referencia D tiene índice C(8,5) + C(6,4) − 1 = 70, y el siguiente índice, la referencia E, dónde el segundo 1 de más a la izquierda llega a su posición final en la posición 6 y los siguientes tres 1s son restituidos a la derecha, es índice C(8,5) + C(6,4) = 71. Los tres 1s de más a la derecha toman todos los valores posibles en (C(3,3) = 1) antes de que el tercer 1 de más a la derecha encuentre su posición final en el lugar 3 como referencia F. Los dos 1s de más a la derecha toman los valores de (C(1,2) = 0) antes de que el segundo 1 de más a la derecha no se mueva; similarmente el 1 de más a la derecha toma todos los valores de (C(0,1) = 0).
Los combinádicos no forman un sistema de numeración, cómo si lo hacen los factorádicos, aunque tiene la apariencia de uno no es un sistema de raíz mixta.
Véase también
Referencias
- Buckles, B. P., Lybanon, M. (1977). «Algorithm 515: Generation of a Vector from the Lexicographical Index». ACM Transactions on Mathematical Software 3 (2). http://portal.acm.org/citation.cfm?id=355732.355739.
- James McCaffrey (Julio de 2004). «Generating the mth Lexicographical Element of a Mathematical Combination».
Enlaces externos
- "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.
- A simple implementation of combinadics in Java by Michael J. Hudson
Categoría:- Combinatoria enumerativa
Wikimedia foundation. 2010.
