Muestra (Combinatoria)

Muestra Concepto: Tupla de r elementos (a1,a1,...,ar) de un n-conjunto A.

Muestra. En Combinatoria una muestra M es la extracción de una cantidad de elementos de un conjunto A dado, más particularmente suele predefinirse la cantidad de elementos a tomar cada vez y entonces se denomina r-muestra pues contiene r elementos. Este valor r se denomina volumen muestral. Las muestras se consideran permutaciones si son ordenadas y combinaciones si el orden no interesa para distinguir una muestra de otra.

Las muestras, permutaciones y combinaciones son los tres pilares de la Combinatoria, una de las ramas de las matemáticas, dedicada al estudio de las posibilidades de formación de distintos tipos de muestras y tiene una gran utilidad para la Probabilística, Matemática Discreta, Estadística, el Análisis de Complejidad de Algoritmos y otras más.

Definiciones.

Sea un conjunto A finito de n elementos se llama r-muestra a cualquier tupla de r elementos (a₁,a₁,...,a_r) de A.

Si al menos un par de elementos a_i, a_j cumple que a_i=a_j; entonces se dice que la r-muestra es una r-muestra con repetición; en caso contrario es una r-muestra sin repetición.

En dependencia de que importe el orden en que se tomaron los elementos, es decir el orden de los a_i en la r-muestra hace que se diferencie una de otra, se dice que es una r-permutación. Si es una r-muestra con repetición entonces será una r-permutación con repetición. Si es una r-muestra sin repetición entonces será una r-permutación sin repetición.

Si no hay orden, es decir si se considera a cualquiera r-permutación de (a₁,a₁,...,a_r) como iguales entre sí, entonces la r-muestra se denomina r-combinación. Si hay repetición de elementos, entonces será una r-combinación con repetición; sino es r-combinación sin repetición.

Tipos de muestras.

Las variantes de r-permutaciones y r-combinaciones conforman todos los tipos posibles de r-muestras sobre A con |A|=n:

• Permutaciones.
  • Permutaciones con repetición.
  • Permutaciones sin repetición.
• Combinaciones.
  • Combinaciones sin repetición.
  • Combinaciones con repetición.

Aunque en algunas fuentes aparecen también las llamadas r-variaciones (simplemente variaciones) o r-arreglos.

El objetivo común ante la presencia de muestras, permutaciones y combinaciones es bien la búsqueda de todas las muestras o el cálculo a priori de la cantidad de posibilidades de conformar cada tipos de muestra, para lo que existen métodos bien definidos a lo largo del desarrollo de la humanidad.

Cada una tiene sus particulariades, orígenes de uso común y formas de aplicación. Veamos todos los casos.

Permutaciones.

Como ya se vio las permutaciones son muestras donde el orden de aparición de los elementos diferencia una muestra de otra, si son los mismos elementos. Por ejemplo, son permutaciones:

• abc, acb, bac, bca, cab, cba.
• (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).

En el primer caso se trata de todas las 3-permutaciones sin repetición del conjunto {a,b,c} escritas como palabras; mientras que el segundo son 3-permutaciones con repetición de los elementos del conjunto {0,1}. Aquí es notable las repeticiones pues se ven varias ternas donde aparece varias veces el cero o el uno.

Ahora bien, las preguntas fundamentales en cada caso son cómo obtener las r-permutaciones sobre un conjunto A con n elementos y cómo podría saberse de antemano el número de formas posibles de r-permutaciones en un n-conjunto (conjunto de n elementos). En dependencia de si se trata de permutaciones con o sin repetición existen métodos distintos. Sin embargo para las r-permutaciones sobre un n-conjunto puede pensarse una forma general:

P(r,n)=k₁k₂...k_r, donde k_i es la cantidad de elementos que pueden disponerse en la posición iésima de la r-muestra.

Permutaciones con repetición.

En este tipo de muestra aunque existe un orden o posicionamiento de los elementos, éstos pueden repetirse en distintos lugares de la misma muestra. Uno de los casos más comunes es nuestro sistema de numeración que al ser posicional hace que cada número natural por ejemplo sea una permutación con repetición para incluir la posibilidad de que una misma cifra pueda significar la cantidad de potencias de 10 que su lugar indica, esto se hace sobre el conjunto de las diez cifras: {0,1,2,3,4,5,6,7,8,9}. Pudiera pensarse que existe una inconsistencia cuando se compara por ejemplo 13 y 133 porque pudiera pensarse que la primera es una 2-permutación y la segunda, una 3-permutación; pero si se reescribe 13 como 013 ya no queda duda.

El método más simple de obtención de las r-permutaciones sobre un n-conjunto A con repetición pudiera ser:

1. Asignar un orden a A, quedando (a₁,a₂,...,a_n)
2. P=(p₁,p₂,...,p_r)={0}^r
3. L = {}

P_r=(a_p1,a_p2,...,a_pr)

1. L=L U {P_r}
2. i=r:
3. Repetir los siguientes pasos hasta que P_r={a_n}^r:
   1. Si p_i no es n:
      1. Incremento p_i

P_r=(a_p1,a_p2,...,a_pr)

1. 1. 1. L=L U {P_r}
   2. De lo contrario:
      1. p_i=0
      2. Si i es distinto de 0:
         1. Decremento i
2. En L quedan las r-permutaciones

En el lenguaje de programación Python pudiera expresarse:

def Permutaciones_con_Repeticion(r, A):
    a = list(A)
    n = len(a)-1
    L = []
    p = [0]*r
    P = [a[j] for j in p]
    L.append(P)
    i = r-1
    p_final = [n]*r
    while p != p_final:
        if p[i] != n:
            p[i] += 1
            P = [a[j] for j in p]
            L.append(P)
            if i!=r-1:
                i=r-1
        else:
            p[i] = 0
            if i:
                i -= 1
    return L

Así pueden obtenerse las r-permutaciones con repetición.

Pero también existe un método de cálculo que determina la cantidad de r-permutaciones con repetición que pueden obtenerse de un n-conjunto:

• Pr_r,n = n^r

Esta fórmula se basa en el hecho aritmético de que por cada n valores de A en la primera posición de la r-partición se pueden poner también cualquiera de los n valores en el 2do puesto y así hasta el lugar r-ésimo. Al final resulta que hay que multiplicar r veces las n ó n^r.

Ejemplos:

¿Cuántas 6-permutaciones pueden formarse con las letras ABCDE? Son 5 letras, por tanto: Pr_6,5 = 5⁶ = 15625.

1. Con 3 tres tiradas de un dado pueden formarse hasta 6³=216 números.

¿Cuántos números de 4 cifras pueden formarse? 9x10³=9000 (la forma queda así debido a que en la cifra de los millares no puede ponerse 0, en el resto sí).

Un caso particular de cálculo de r-permutaciones con repetición sobre un n-conjunto A es cuando se quieren determinar la cantidad de subconjuntos de A. Para ello se crea una n-upla cuyos elementos serían la existencia (V) o la ausencia (F) de cada elemento de A. Ahora la pregunta cambia a cuántas n-uplas puden conformarse con {F,V} que es lo mismo que 'Pr_n,2 = 2ⁿ.

Permutaciones sin repetición.

A las permutaciones sin repetición también suele llamársele variaciones o arreglos y consisten básicamente en tomar en orden hasta r los elementos de A como mismo se haría de una bolsa. Para la primera posición de la r-permutación hay n posibilidades de escoger; para la segunda, como ya se tomó un elemento, quedan n-1; para el tercer puesto, n-2 y así sucesivamente hasta el lugar r donde hay n-r+1 variantes para escoger. En resumen, pueden formarse P_r,n r-permutaciones sin repetición sobre un n-conjunto, donde:

• P_r,n=n(n-1)(n-2)...(n-r+1).

En el caso que r=n, la fórmula queda:

• P_n,n=P_n=n!.

No existe una fórmula para cuando r>n porque al extraerse los n elementos de A todavía quedan lugares por llenar en la r-muestra y ya no hay más elementos.

La construcción de las distintas permutaciones suele realizarse recorriendo el [[Bosque (Grafo)|bosque]] cuyos árboles tienen una raíz que puede ser cualquiera de los n elementos de A, se marca ese elemento y derivan n-1 ramas para los elementos restantes, luego a partir de cada uno de estos se trazan n-2 ramas con los otros elementos remanentes y así hasta completar la profundiddad r.

Bosque de árboles de derivación de elementos de A

Combinaciones.

Tras la idea de la combinación subyace el hecho de no tener en cuenta el orden de los elementos, solo la presencia de ellos en la muestra basta para identificarlas. Aunque en el caso de las combinaciones con repetición de elementos pudiera representarse como un conjunto, cuando se permite la repetición no funcionaría porque los conjuntos no lo admiten. Así que normalmente suele mostrarse como r-uplas.

Ejemplos

• ab, ac, bc son las 2-combinaciones sin repetición de {a,b,c}.
• aa, ab, ac, bb, bc, cc son las 2-combinaciones con repetición de {a,b,c}.

También en el caso de las r-combinaciones suele quererse conocer cómo obtenerlas todas y cuántas hay o habrá.

Combinaciones sin repetición.

El conteo del total de r-combinaciones sin repetición sobre un n-conjunto viene dado por el hecho quitar de la cantidad de r-permutaciones ó P_r,n las permutaciones que pueden hacersele a cada r-muestra que sería P_r,r. Dividiendo queda: P_r,n/P_r,r=P_r,n/r!. Este resultado es bien conocido y se identifica con la siguiente notación:

• 

Cuyo nombre también es el de coeficiente binomial.

Es fácil percibir que las r-combinaciones de un n-conjunto son sus subconjuntos de longitud r. Por tanto, el método constructivo se centra en obtener todos los r-subconjuntos de A.

Combinaciones con repetición.

Cuando en las combinaciones se admite la repetición de elementos, el conteo (y la construcción) del total de r-combinaciones con repetición sobre un n-conjunto toma la forma:

1. Se asocia a A el

subconjunto N_n de los n primeros naturales mediante el isomorfismo R={<1,a₁>,<2,a₂>,...,<n,a_n>}.

1. L = {}

Para toda r-muestra M=(k₁,k₂,...,k_r) donde k_i es un elemento de N_n y k₁<=k₂<=...<=k_r:

1. 1. Invirtiendo el isomorfismo R, se obtiene a partir de M la r-muestra S.
   2. L=L U {S}
2. En L quedan las r-combinaciones con repetición de A

Antes de contabilizar las combinaciones obtenidas por el método anterior, se puede hacer una segunda asociación biunívoca entre M y un r-conjunto O conformado según O={k₁+0,k₂+1,...,k_r+r-1}, donde O será la forma de todos los r-subconjuntos de {1,2,...,n,n+1,...,n+r-1}, que es lo mismo que las r-combinaciones de un (n+r-1)-conjunto, que se define como:

• 

Fuentes.

1. K. Ribnikov. Análisis Combinatorio. Editorial Mir. Moscú, 1988. Páginas 17-23.
2. I. Bronshtein, K. Semendiaev. Manual de Matemáticas para ingenieros y estudiantes. 2da Edición. Editorial Mir. Moscú, 1973. Páginas 186-188.

Se sugieren las categorías Combinatoria y Análisis Combinatorio