Combinádico

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

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Factorádico — Saltar a navegación, búsqueda En combinatoria, factorádico (del inglés factoradic ) es un sistema numérico especialmente construido. El sistema factorádico proporciona un índice lexicografico para permutaciones por lo que tiene potencial… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”