Medellín, abril de 2023
Variaciones,
permutaciones y combinaciones
Permutaciones
Una permutación es el número de maneras distintas en que se pueden ordenar los elementos de un conjunto.
1 Sí importa el orden de los grupos, ya que el intercambio entre dos elementos distintos genera una nueva permutación
2 No se repiten los elementos, ya que de repetirse o ser iguales entre si, al intercambiarlos no se genera una nueva permutación
Ejemplo sea el conjunto
C = {a, b, c, d, e, f}
Cuantos grupitos de 6 letras, se pueden formar, sin que haya repetición
de elementos. En este ejemplo:
El primero puesto lo puede ocupar uno de los 6, el segundo, uno de los cinco restantes, el tercero, uno de los cuatro restantes, el cuarto uno de los tres restantes, el quinto uno de los dos restantes, y el sexto sólo 1
P66 =6x5x4x3x2x1 = 6! =720 permutaciones
Si se permitiera que las duplas tengan elementos repetidos de los dellconjunto C, entonces las séxtuplas serían más =: 6! + muchas otras, las que tienen 6 veces el mismo elemento, las que tienen 5 veces el mismo elemento y así sucesivamente.
Ahora veamos que son las combinaciones:
Si tenemos el conjunto C = {a, b, c, d} =. Vamos a formar grupos de tres letras, en los que no se pueden repetir elementos y en las cuales el orden no importa (a, b, c) es lo mismo que (b, c, a) o (c, a, b)
Las combinaciones son
abc, abd, bcd, cad = 4
El primer puesto lo pueden ocupar 4 letras, el segundo 3 y el tercero 2
4x3x2 = 24 Pero si dejamos esto así,
estaríamos encontrando el número de permutaciones, pero como abc, acb, bac,
bca,cab, cba son la misma combinación, es decir debemos dividir el resultado 24
por 6 = 3x2
Total, 4x3x2/(3x2) = 4 abc, abd, bcd y cad
Tratando de generalizar estos dos ejemplos:
Permutaciones:
Tenemos un conjunto con n elementos diferentes y queremos hacer grupitos de r elementos r<n, que sean diferentes y que se consideren como arreglos diferentes, los que tienen los mismos elementos, pero en orden diferente.
El primer lugar lo puede ocupar uno de los n elementos, el segundo uno de loa n -1 elementos, el tercero de los n -2 restantes y el r(esimo) n – r +1
nPr= Pnr permutación de n elementos diferentes, agrupados en grupitos de r elementos.
= n(n-1) (n-2)………..(n-r +1) = n!/(n-r)! (1)
Combinaciones
Tenemos un conjunto con n elementos diferentes y queremos hacer grupitos de r elementos r<n, que sean diferentes y que, no obstante, su orden, se consideren como arreglos iguales, los que tienen los mismos elementos, pero en orden diferente.
El primer lugar lo puede ocupar uno de los n elementos, el segundo n -1 elementos, el tercero n -2 y el r(esimo) n – r +1
nCr = Cnr Combinación de n elementos diferentes, agrupados en grupitos de r elementos.
= n(n-1)(n-2)………..(n-r +1)/r! (2)
Las fórmulas (1) y (2) son las más importantes del análisis combinatorio, pero no son las únicas. Se pueden hacer permutaciones nPn, permitiendo elementos repetidos, etc.
Se ha introducido en concepto de variación. De todas maneras se parte de un conjunto C con n elementos y los vamos a variar, permutar o combinar en grupitos de r elementos r=<n , sacados del conjunto C.
Figura 1, Permutaciones, combinaciones y variaciones.
Preguntas que se deben hacer para averiguar si se trata de una
variación, una permutación o una combinación y sus respectivas fórmulas.
Quiero hacer una explicación especial para el caso PRn a,b
¿Cuántas palabras (con o sin sentido) se pueden formar con las letras de la palabra agronomía? Hay 9 letras, pero a tiene dos repeticiones y o tiene dos repeticiones
Como entran todos los elementos del conjunto, se trata de una Permutación y como hay dos elementos repetidos en la palabra agronomía, estaremos hablando de
PR9 2,2 = 9! / (2! *2!) = 90720 permutaciones.
Encontrar el número de formas en las cuales m + n objetos pueden ser divididos en dos grupos, que contengan m y n elementos cada uno.
Esto es claramente equivalente a encontrar el número de combinaciones de m
+ n objetos diferentes en un grupo de m. Esto es de acuerdo con la fórmula de
combinaciones Cm+n
n (m+n)!/((n!)(m+n-n)!) =
(m+n)!/((m!)(n!))
Si m = n, los dos grupos son iguales, por lo que hay que dividir por 2! el número de combinaciones.
(2m)! /((m)!) (m!)2!)
Para encontrar el número de formas en las cuales m + n + p objetos pueden ser divididos en tres grupos, que contengan m, n y p elementos respectivamente.
Primero dividimos en dos grupos, el primero contiene n+p y el segundo m
Como en el caso anterior
Cm+n+p n+p = (m+n+p)! /((m!) (n+p)!)
Luego el grupo n+p lo dividimos en dos grupos, el primero contiene n y el segundo p cosas.
Cn+p n = (n+p)! /((n!) (p!))
El número total de combinaciones será Cm+n+p n+p * Cn+p n
=(m+n+p)! (n+p)!/((m!)(n+p)!(n!)p(¡)) = (m+n+p)!/((m!)(n!)(p!))
Ejemplo numérico 1
De un grupo de 7 ingleses y de otro de 4 americanos, se va a formar un comité de 6 personas, pero el comité debe tener 2 americanos. Cuántas formas posibles hay de formar ese comité?
El número de formas en que pueden escogerse los americanos es C42 y el número de formas en que pueden escogerse los ingleses es C74
El número de formas en que se puede escoger ese comité es C42* C74
(4! / ((4-2)!(2!)))*(7!/((4!)((7-4)!) = 4! * 7! /((2!) (2!) (4!)(3!)) = 7!/ 24 = 210 casos
Si formulamos la pregunta de otra forma:
El comité que vamos a formar debe contener mínimo 2 americanos y no menos de 4.
Los casos en que hay dos americanos = 210
Los casos en que hay tres americanos: C43* C73 = (4!)/(3!*1!) * (7!)/((3!)(4!)) = 140
Los casos en que hay 4 americanos C44* C72 = (7!)/((2!)(5!) = 21
La respuesta es 210 + 140+ 21 = 371
Ejemplo numérico 2
Tenemos un grupo de 7 consonantes diferentes y de 4 vocales diferentes. Cuántas palabras, (con o sin sentido) se pueden formar que contengan 3 de esas consonantes y dos de esas vocales.
El número de formas de escoger las tres consonantes es C73 = (7!)/((3!) (4!))
El número de formas de escoger las 2 vocales es C42 =
(4!)/((2!)(2!)) y cada una de estos grupos tiene cinco letras las cuales pueden
ser organizadas de 5! Veces.
El número requerido de palabras es [(7!)/((3!)(4!)]* [(4!)/((2!)(2!))][5!] = 25200
Ejemplo numérico 3
Cuántas palabras pueden ser formadas con las letras de la palabra “article”, de tal forma que las vocales ocupen los lugares pares
El conjunto de letras es {C1, C2, C3, C4, V1, V2 , V3} Ci consonante, Vi vocal
La palabra a formar es así CVCVCVC
Para las vocales hay tres puestos y el orden es importante, por tanto, el número de formas de escoger las vocales es P33 permutación de 4 elementos en grupos de a 3 = 3! = 6
Para las consonantes hay cuatro puestos y el orden es importante, por tanto, el número de formas de escoger las consonantes es P44 permutación de 4 elementos en grupos de a 4 = 4! = 24
El número requerido de palabras es 6x26 = 144
La mayoría de la teoría se sacado del libro “Higher Algebra, by Hall and Knight” Tercera edición 1889. Pero también se han tomado conceptos de otros textos y papers. En algunos hacen diferencia entre variaciones y permutaciones, y en otros, como el principal, no existe la palabra variación.
Realmente hay casos en los que no distinguen las variaciones de las permutaciones. En ese sentido, Hall and Knigth parece tener razón, en fundir ambos conceptos en el concepto permutación.
Veamos un ejemplo teórico. (No4)
Encontrar el número de formas en cual n objetos puede ser arreglado entre todos ellos al mismo tiempo, donde p elementos son exactamente iguales, de cierta clase, q elementos son exactamente iguales, pero de otra categoría y r elementos son exactamente iguales, en otra categoría y el resto son todos diferentes.
p + q `+ r < = n
Tomemos n letras, supongamos que p de ellas son a, q son b y r son c y el
resto letras diferentes.
Sea x el número requerido de permutaciones.
Si las p letras “a” fueran permutadas, el número de permutaciones, sin alterar la posición de las diferentes letras, nosotros tendríamos p nuevas permutaciones. Si este cambio fuera hecho en cada una de las x permutaciones, el número total de estas sería x(p!).
En forma similar, si las q letras “b” fueran permutadas, el número total de permutaciones sería
x(p!)(q!)
En idéntica manera, si las r letras c fueran permutadas, el número total de permutaciones sería
x(p!)(q!)(r!)
Pero ahora las n letras fuesen todas diferentes y admitirían (n!) permutaciones
x(p!)(q!)(r!) = (n!)
x = (n!)/((p!)(q!)(r!)
Ejemplo numérico de este ejemplo teórico (No5)
Cuantas permutaciones pueden ser hechas con las letras de la palabra “assassination”, tomando todas las letras.
Hay 13 letras, 4 son s, 3 son a, i son 2 y n son 2 Letras repetidas. No repetidas “t” y “o”
Note que: 4 + 3 + 2 + 2 = 11<13
No obstante, de acuerdo con la fórmula del ejercicio teórico, el número de permutaciones será:
= (13!)/((4!)(3!)(2!)(2!)) = 13*11*10*9*8*7*3*5 = 10’810800 permutaciones.
Cómo se puede observar, en este caso no hay claridad en la separación de conceptos entre variación y permutación.
Ejercicios
1.De cuántas maneras pueden sentarse 10 personas en un banco si hay 4 sitios disponibles? R_5040
2.En una clase de 10 alumnos van a distribuirse 3 premios. Averiguar de cuántos modos puede hacerse si: 1. los premios son diferentes. 2. los premios son iguales. Una misma persona no puede recibir más de un premio: R_720 y _120
3. Cuántos arreglos diferentes se pueden hacer tomando 5 de las letras de la palabra equation. R_ P8 5
4.
Si cuatro veces el número de permutaciones de n objetos, tomados de en grupos
de a tres, es igual a cinco veces el número de permutaciones de n – 1 objetos,
tomados en grupos de 3. Encontrar n. R_15
5.
De cuántas formas pueden 17 bolas de billar ser organizadas, si 7 de ellas son
negras, 6 son rojas y 4 blancas. Explicar el procedimiento. R_4084080
6. Cuantas permutaciones pueden ser hechas con las letras de
la palabra triangle. Cuantas de estas
pueden empezar por la letra t y terminar con la letra e? R_40320 y _720
7. Un hombre tiene 6 amigos, de cuantas maneras puede
invitarlos a cenar en su casa. (podria ser de a 1, de a 2, de a 3, de a 4, de a
5 y de a 6) R_ 63.
8. En barco carguero hay establos, cada uno con
capacidad para 12 animales. Hay vacas,
caballos y terneros. (no menos de 12 de cada uno) para ser embarcados. De
cuantas maneras puede el barco llevarlas? R_531444
9. De cuantas maneras pueden 5 cosas ser divididas
entre dos personas.R_30
Nota
Las siguientes anotaciones tienen igual significado nPr y Pnr, nCr y Cnr
Juan Fernando Sanín E
juanfernando.sanin@gmail.com μ