Tema3

Maestría en Enseñanza de las Matemáticas Combinaciones y permutaciones Tema 3: Permutaciones circulares y Permutaciones de elementos no todos distintos

Instituto de Matemáticas Grupo Kernel

Universidad de Antioquia Facultad de Ciencias Exactas y Naturales Instituto de MatemáticasGrupo Emac

2

Combinaciones y permutaciones

1.

Permutaciones circulares

Queremos resolver el problema de encontrar el número de formas posibles de colocar n objetos distintos en n lugares equidistantes sobre un circulo, si además consideramos las rotaciones como configuraciones iguales. Supongamos que conocemos el valor de este número para cada n y denotemoslo por (P C)(n). Lema 1.1. Para cada n natural, (P C)(n) = (n − 1)! Demostración. Si no consideramos configuraciones iguales debido a rotaciones, se tendrían n! configuraciones. Ahora, cada permutacion tiene asociada n rotaciones, así (P C)(n) =

n! = (n − 1)!. n

Ejemplo 1.1. Suponga que tenemos una mesa circular con 7 sillas.¿De cuántas formas se pueden acomodar 7 personas, de modo que dos personas determinadas no queden juntas? Solución: Se pueden formar (P C)(5) = 4! con las otras 5 personas. Luego tenemos 5 formas de acomodar una de las personas en la mesa, y posteriormente quedan 4 formas de acomodar la última persona, por tanto la respuesta es 4! × 5 × 4 = 480.

2.

Permutaciones de elementos no todos distintos

¿Cuántos anagramas posee la palabra MATEMATICA?. Es claro que la respuesta no puede ser P10 = 10!, pues la palabra MATEMATICA tiene letras repetidas, así que 10! en realidad excede el número de anagramas que se obtienen. Note que la palabra MATEMATICA contiene 3 veces la letra A, dos veces la letra M y dos veces la letra T, el resto de letras está 3,2,2 una sola vez. Denotamos por P10 el número de anagramas, vamos a calcularlo: 3,2,2,1,1,1 3 P10 = C10 C72 C52 C31 C21 C11 =

5! 3! 2! 1! 10! 10! 7! · · · · · = . 3!7! 2!5! 2!3! 1!2! 1!1! 1!0! 3!2!2!

Ahora, es fácil ver el siguiente resultado Lema 2.1. Pna1 ,a2 ,...,am =

n! a1 !a2 !...am !

(m ≤ n) donde a1 + a2 + . . . + am = n.

3

Combinaciones y permutaciones

3.

Ejercicios

3.1.

Ejercicios resueltos

1. ¿De cuantas formas podemos sentar 4 hombres y 4 mujeres en una mesa circular con 8 sillas, de tal forma que las personas del mismo sexo no queden juntas? Solución: Existen (P C)(4) = 3! formas de sentar las mujeres inicialmente, luego ubicamos a los hombres en los 4 lugares restantes entre las mujeres, y esto puede hacerse de 4! formas. Así la respuesta es 3! · 4! = 144. 2. Una partícula ubicada en el punto (x, y) ∈ Z2 , puede moverse para el punto (x + 1, y) o para el punto (x, y + 1) (a la derecha o arriba). ¿Cuántos caminos puede tomar la partícula para llegar al punto (n, m) (con n, m números naturales) partiendo de (0, 0). Solución: La partícula debe desplazarse n veces a la derecha y m veces hacia arriba, tomando los desplazamienos a la derecha como elementos iguales y los desplazamientos hacia arriba también como iguales, se tiene que el número de caminos es igual a n,m = Pm+n

3.2.

(n + m)! n m = Cn+m = Cn+m . n! · m!

Ejercicios propuestos

Permutaciones circulares 1. ¿De cuantas formas n personas se pueden sentar en una mesa circular con n sillas, de tal forma que dos personas siempre permanezcan juntas? y ¿de modo que k personas (k < n) permanezcan juntas? 2. Se tienen n matrimonios en una fiesta, ¿de cuántas maneras pueden formar una circunferencia, de tal forma que cada mujer este al lado de su esposo? Permutaciones de elementos no todos distintos 1. ¿Cuántos anagramas de la palabra PERFECCION comienzan con una vocal? 2. ¿Cuántos números de 7 dígitos mayores que 3500000 pueden ser formados usando solamente los números 1, 2, 2, 3, 3, 3, 7?