Permutaciones
Permutaciones, Variaciones y Combinaciones con y sin repetición
Variaciones, Permutaciones, Combinaciones
Similitudes entre Variaciones y Permutaciones
Muchos autores consideran variaciones y permutaciones como el mismo concepto. En estos casos tenemos
Permutaciones de n elementos tomados de a m.
Permutaciones de n elementos tomados a n.
Yo prefiero denominar al primer caso como variaciones, y dejar el termino permutaciones para el segundo caso.
En cualquier caso es imporante conocer esto a la hora de interpretar distitos autores como también de programar:
A la hora de hablar de permutaciones, también hablamos de variaciones y viceversa.
Diferencias entre Variaciones y Combinaciones
Variaciones o Permutaciones y combinaciones no son la misma cosa.
Las variaciones/permutaciones se diferencian de las combinaciones en una cosa: el orden.
En las variaciones y permutaciones si importa el orden.
Por ejemplo ABC <> BCA, estos dos casos cuentan 2.
En las combinaciones no importa el orden.
Por ejemplo ABC = BCA. estos dos casos son la misma cosa y cuentan como 1.
Repeticiones
Existen dos conceptos asociados a las repeticiones en variaciones o permutaciones y combinaciones.
Repeticiones dentro de un conjunto de datos o arreglo bajo estudio.
Repeticiones en el uso, aplicación o asignacion de los conjuntos de datos.
1. Repeticiones en un conjuntos de datos
Las repeticiones dentro de un conjunto de datos hace que la cantidad de variaciones o permutaciones disminuya, es decir, sea menor que las variaciones sin repeticiones.
Ejemplo con letras:
Por ejemplo, la cantidad de variaciones o permutaciones de 5 elementos distintos (ej: a,b,c,d,e) o sin repetidos es 5! (como se ve más abajo).
Sin embargo la cantidad de variaciones de 5 elementos no distintos o con reetición, porque 3 son iguales (ej: a, a, a, b, c) es 5!/3!.
En consecuencia la cantidad de permutaciones o variaciones disminuye porque en realidad estamos permutando dos subconjuntos de datos dentro de un conjunto de 5 elementos. ((a, a, a) y (b,c)).
En general:
Permutaciones de elementos repetidos de un conjunto = P(n, n1, n2...) = n! / (n1! x n2! ...)
2. Repeticiones en el uso, aplicación o asignación de un conjunto de datos
Las repeticiones del uso, aplicación o asignación de un conjunto de datos hace que la cantidad de permutaciones aumente, es decir sea mayor que las variaciones sin repeticiones.
En este caso no hablamos de los elementos repetidos dentro de un conjunto de datos sino del uso repetido de una permutación dentro de un arreglo de permutaciones de un conjunto.
Ejemplo de un bit y un byte:
Un bit puede considerarse como un conjunto de dos valores posibles [0,1]. Y es facil que la cantidad de valores posibles o de variaciones posibles son solo dos. Es decir que C(2,1) = 2! / (1!1!) = 2. Es decir que un bit puede valer solo uno de dos valores, un cero o un uno. Pero luego estos dos estados los puedo usar para armar un byte (un conjunto de 8 bits. En este caso estamos repitiendo 2 veces las variaciones de un bit. Es decir:
Variaciones de un byte = 2x2x2x2x2x2x2x2 = 2 elevado a la 8 = 256
En general:
Permutaciones con repetición de variantes de un conjunto = V(n, m)cr = m eñevado a la m.
Ejemplo de tratamiento:
Un grupo de cuatro tratamientos que se asignan aleatoriamente a 10 árboles daría 4 a la 10 variantes de asignación posible, ya que a cada árbol se le puede asignar aleatoriamente uno de los 4 tratamientos.
Cada asignación de tratamiento es un suceso aleatorio independiente del otro y por lo tanto se puede repetir. (Es con repetición)
Ejemplo de día de cumpleaños:
El grupo de 365 días del año se asigna aleatoriamente a 25 personas para ver si alguna de ellas cumple el mismo día. Esto da como resultado 365 elevado a la 25.
Cada asignación de fecha a cada persona es un suceso aleatorio independiente del otro y por lo tanto se puede repetir.
Variaciones o permutaciones de n elementos, sin repetición
(cuando todos los elementos son diferentes) y sin reemplazo
Las permutaciones son arreglos de n elementos en un orden específico. No se permite la repetición de elementos..
Este es el caso más simple, y comprende todas las variantes posibles en las que se pueden reordenar los elementos de un conjunto de datos. Esto en otras palabras corresponde a la definición de factorial.
En efecto el primer orden de un comjunto de datos es n luego la forma de ordenarlo es n-1 y luego n-2 y así sucesivamente hasta 1. Es decir que:
P(n,n) = V(n,n) = n!
Cuándo se usa: Se usa cuando tienes un conjunto de n elementos y quieres saber cuántas maneras distintas puedes ordenarlos todos.
Ejemplo de un bit:
Un bit puede considerarse como un valor que puede tomar uno de dos valores de un cojunto de datos {0,1}
Dado este cojunto de datos la cantidad de formas en que el mismo puede variar es:
P(2,2) = 2! = 2
Ejemplo de 8 ciudades:
Tenemos un conjunto de 8 ciudades: { CABA, BA, SF, MZA, CBA, SL, SJ, LR }. Para ordenar las 8 ciudades en una ruta en la que cada ciudad se visita una vez.
P(8,8) = 8! = 8x7x6x5x4x3x2x1 = 40.320
Variaciones o permutaciones de n elementos, con repetición m
(cuando todos los elementos pueden o no repetirse)
Las variaciones (también llamadas "permutaciones con repetición") son arreglos de n elementos en un orden específico, pero permitiendo la repetición de elementos una cantidad m de veces.
P(n,m)cr = V(n,m)cr = n elevado a la m
Cuándo se usa: Se usa cuando tienes nnn elementos y quieres saber cuántos arreglos de longitud kkk puedes hacer, permitiendo que los elementos se repitan.
Ejemplo de código de 8 letras:
Para crear un código de longitud 8 usando 8 letras (donde se pueden repetir letras). la formula es:
P(n,m)cr = 8 elevado a la 8 = 8x8x8x8x8x8x8x8 = 16.777.216
Otros ejemplos:
Al comienzo de este texto en el apartado de "Repeticiones" (más arriba) se plantean los ejemplos de un bit y un byte, como tambien el ejemplo del día de cumpleaños.
Variaciones de n elementos tomados de a m, sin repetición
(cuando todos los elementos son diferentes) y sin reemplazo
(cuando no vuelvo a poner la observación que saqué)
Requisitos
1. Existen n elementos diferentes disponibles. (Esta regla no se aplica si algunos de los elementos son idénticos a otros. Por ejemplo: AAC, no cumple esta regla porque se reptite A).
2. Seleccionamos m de los n elementos (sin reemplazo, no reinserto la observación que obtuve).
3. Consideramos que los reordenamientos de los mismos elementos son secuencias diferentes. (La permutación de ABC difiere de la de CBA y se cuentan de forma separada. Esto implica que sí importa el orden.).
Si se satisfacen los requisitos anteriores, el número de permutaciones (o secuencias) de m elementos seleccionados entre n elementos disponibles (sin reemplazo) es:
P(n,m) = n! / (n-m)!
o
V(n,m) = n! / (n-m)!
o
n*(n-1)*(n-2)*(n-m+1)
Interpretación de la regla de las permutaciones sin repetición y sin reemplazo
Cuando utilizamos los términos permutaciones, variaciones, acomodos o secuencias, implicamos que si se toma en cuenta el orden, (si importa el orden), en el sentido de que diferentes ordenamientos de los mismos elementos se cuentan por separado.
De acuerdo con la regla factorial, n diferentes elementos pueden acomodarse de n! diferentes maneras.
Entonces un conjunto de elementos no repetidos pueden ordenarse de tantas maneras como el factorial lo indique.
Ejemplo ABC (n elementos tomados todos)
Las letras ABC se pueden acomodar de seis formas distintas: ABC, ACB, BAC, BCA, CAB, CBA.
(Más adelante nos referiremos a las combinaciones, en las que tales acomodos no se cuentan por separado).
Si aplico la fórmula: V(3,3) = 3!/0! = 3x2x1/1 = 6
Si aplico la formula P(3) = 3!
De acuerdo con la regla factorial, n diferentes elementos pueden acomodarse de n! diferentes maneras. Algunas veces tenemos n elementos diferentes, pero necesitamos seleccionar sólo algunos de ellos en vez de todos.
Ejemplo ABC (n elementos tomados de a m)
Supongamos que queremos calcular de cuantas maneras distintas se pueden ordenar las tres letras ABC pero tomadas de a grupos de dos: AB, BC, BA, CB, AC, CA
(Más adelante nos referiremos a las combinaciones, en las que tales acomodos no se cuentan por separado).
Si aplico la fórmula: V(3,2) = 3!/1! = 3x2x1/1 = 6
P(3,2) es exactamente la misma formula con distinto nombre (Permutaciones en lugar de variaciones)
Resumen:
Existen dos tipos de variaciones o permutaciones sin repetición:
Variaciones o permutaciones de n elementos tomados todos juntos. V(n) = n!
Variaciones o permutaciones de n elementos tomados de a m. V(n,m) = n! / (n-m)!
Variaciones o permutaciones de n elementos tomados de a m, con repetición (cuando algunos elementos son iguales) y sin reemplazo dentro de un cojunto
Requisitos
1. Existen n elementos disponibles, y algunos de ellos son idénticos a otros. (Por ajemplo AAC, es un arreglo dónde la A se repite dos veces)
2. Seleccionamos todos los n elementos (sin reemplazo).
3. Consideramos que los reordenamientos de los mismos elementos son secuencias diferentes. (Por ejemplo AAC es distinto de CAA)
Si los requisitos anteriores se satisfacen y si existen n elementos con n1 iguales, n2 iguales, . . . , nk iguales, el número de permutaciones de los n elementos es:
P(n, n1..nk = n!/(n1! x n2! x...xnk!)
Ejemplo:
Selección del género Los ejemplos clásicos de la regla de permutaciones son los que demuestran que las letras de la palabra Mississippi se pueden ordenar en 34,650 formas diferentes, mientras que las letras de la palabra statistics se pueden ordenar en 50,400 formas.
Ahora consideraremos una aplicación diferente.
Al diseñar una prueba de un método de selección del género con 10 parejas, un investigador sabe que existen 1024 secuencias diferentes de género posibles cuando nacen 10 bebés. (Utilizando la regla fundamental del conteo, el número de posibilidades es 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 1024). Diez parejas utilizan un método de selección del género, y los 10 nacimientos incluyen 8 niñas y 2 niños.
a. ¿De cuántas maneras se pueden acomodar en secuencia 8 niñas y 2 niños?
b. ¿Cuál es la probabilidad de tener 8 niñas y 2 niños en 10 nacimientos?
c. ¿La probabilidad del inciso b) sirve para evaluar la eficacia del método de selección del género?
a. Tenemos n = 10 nacimientos, con n1 = 8 iguales (niñas) y n2 = otros 2 (niños) que son iguales. El número de permutaciones se calcula de la siguiente manera:
P(n,m) = n! /n1! n2!
P(10,8)=10!/8!2!
P(10,8)=3,628,800/80.640=45
b. Puesto que hay 45 formas diferentes de ordenar a 8 niñas y 2 niños, y existe total de 1024 arreglos diferentes posibles, la probabilidad de 8 niñas y 2 varones está dada por:
P(8 niñas y 2 niños) = 45/1024 = 0.0439.
c. La probabilidad de 0.0439 no es la probabilidad que se debe usar para evaluar la eficacia del método de selección del género. En vez de la probabilidad de que haya 8 niñas en 10 nacimientos, debemos considerar la probablidad de 8 o más niñas en 10 nacimientos, que es 0.0547.
El ejemplo anterior considera n elementos, cada uno perteneciente a una de dos categorías. Cuando sólo hay dos categorías, podemos estipular que x de los elementos son iguales y que los otros n x elementos también son iguales, de manera que la fórmula de las permutaciones se simplifica a:
P(n,m) = n! /m! (n-m)!
Regla de las combinaciones
Combinaciones sin repetición y sin reemplazo
Las combinaciones son selecciones de m elementos de un conjunto de n elementos sin importar el orden y sin permitir repetición.
Requisitos
1. Tenemos un total de n elementos diferentes disponibles.
2. Seleccionamos r de los n elementos (sin reemplazo).
3. Consideramos que los reordenamientos de los mismos elementos son iguales. (La combinación ABC es igual que CBA).
Si se satisfacen los requisitos anteriores, el número de combinaciones de m elementos seleccionados a partir de n elementos diferentes es:
C(n,m) = n! /m! (n-m)!
Cuándo se usa: Se usa cuando quieres seleccionar m elementos de un conjunto de n elementos sin que importe el orden y sin repetir elementos.
Ejemplos:
Pildoras: Para seleccionar 3 píldoras de un conjunto de 10. La fórmula es.
C(10,3) = 10! / 7! x 3! = 120
Fase I de una prueba clínica Cuando se prueba un nuevo fármaco en seres humanos, generalmente se realiza una prueba clínica en tres fases. La fase I se lleva a cabo con un número relativamente pequeño de voluntarios sanos. Suponga que deseamos tratar a 8 seres humanos saludables con un nuevo fármaco y que tenemos 10 sujetos voluntarios disponibles.
a. Si los sujetos se seleccionan y se tratan en secuencia, de manera que la prueba se suspenda si alguno de ellos presenta cualquier reacción adversa,
¿cuántos arreglos secuenciales diferentes son posibles si se seleccionan 8 personas de las 10 disponibles?
b. Si se seleccionan 8 sujetos de los 10 disponibles, y los 8 sujetos elegidos se tratan al mismo tiempo, ¿cuántos grupos de tratamiento diferentes son posibles?
Observe que en el inciso a) el orden es importanteporque los sujetos se tratan de manera secuencial y la prueba se suspende si alguno de ellos muestra alguna reacción adversa específica. Sin embargo, en el inciso b), el orden de selección es irrelevante porque todos los sujetos reciben tratamiento al mismo tiempo.
a. Puesto que el orden es importante, buscamos el número de permutaciones de m = 8 personas seleccionadas de las n = 10 disponibles.
V(10,8) = 10!/(10-8)! = 10!/2! = 1,814,400.
encontramos que el número de permutaciones es de 1,814,400.
b. Puesto que el orden no es importante, buscamos el número de combinaciones de r = 8 personas seleccionadas de las n 10 disponibles. Obtenemos:
C(10,8) = 10!/8!(10-2) = 10!/8!2! = 10 x 9 x 8! /8! 2! = 45
Cuando se toma cuenta el orden, hay 1,814,400 permutaciones, pero cuando no se toma en cuenta el orden, existen 45 combinaciones.
Combinaciones con repetición
Las combinaciones con repetición permiten seleccionar m elementos de un conjunto de n elementos, permitiendo la repetición y sin importar el orden.
C(n,m)cr =(n+m-1)! / m!(n-1)!
Cuándo se usa: Se usa cuando quieres seleccionar m elementos de un conjunto de n elementos permitiendo repeticiones y sin importar el orden.
Ejemplo:
Selección de bolas de colores
Seleccionar 3 bolas de 5 colores diferentes, pudiendo repetir colores.
Antes de resolver, debe notarse que no se especifica si se puede elegir con reemplazo o si hay una cantidad ilimitada de botas de los 5 colores. Solo se dice que se pueden repetir colores.
El concepto clave aquí es que cada tipo de elemento (en este caso, cada color de bola) se puede seleccionar múltiples veces. No estás limitado a una única bola por color; puedes tener varias bolas del mismo color.
n: 5 (tipos diferentes de bolas, es decir, 5 colores).
m: 3 (número de bolas a seleccionar).
C(5,3)cr=(5+3-1)! / 3! (5-1)! = 7! / (3!x4!) = 35
Hay 35 maneras diferentes de seleccionar 3 bolas de 5 colores diferentes cuando se permite la repetición de colores. Esto significa que puedes tener combinaciones como:
3 bolas rojas
1 bola roja, 1 bola azul, 1 bola verde
2 bolas amarillas, 1 bola negra
Y así sucesivamente.