8.3: Permutaciones

Let\(A\) Ser un conjunto finito con\(n\) elementos. Para\(1\le r\le n\), una \(\mathbf{r}\)-permutación de\(A\) es una selección ordenada de\(r\) distintos elementos de\(A\). En otras palabras, es la disposición lineal de\(r\) distintos objetos\(a_1a_2\ldots a_r\), donde\(a_i\in A\) para cada uno\(i\). El número de\(r\) -permutaciones de un conjunto de\(n\) elementos se denota por\(P(n,r)\). También aparece en muchas otras formas y nombres.

• El número de permutaciones de\(n\) objetos, tomadas\(r\) a la vez sin reemplazo.
• El número de formas de organizar\(n\) los objetos (en una secuencia), tomadas\(r\) a la vez sin reemplazo.

Todos ellos se refieren al mismo número\(P(n,r)\). Las palabras clave son:

1. “Permutación” o “arreglo”, ambas sugieren que el orden sí importa.
2. “Sin reemplazo” significa que las entradas en la permutación/arreglo son distintas.

En algunos libros de texto, la notación también\(P(n,r)\) se escribe como\(P_r^n\) o\(_nP_r\).

Ejemplo\(\PageIndex{1}\label{eg:perm-01}\)

Las 1-permutaciones de\(\{a,b,c,d\}\) son

\[\begin{array}{llll} a, & b, & c, & d. \end{array} \nonumber\]

En consecuencia,\(P(4,1)=4\). Las 2 permutaciones de\(\{a,b,c,d\}\) son

\[\begin{array}{lll} ab, & ac, & ad, \\ ba, & bc, & bd, \\ ca, & cb, & cd, \\ da, & db, & dc. \end{array} \nonumber\]

De ahí,\(P(4,2)=12\). ¿Cuáles son las 3 permutaciones y las 4 permutaciones de\(\{a,b,c,d\}\)? ¿Puede explicar por qué los números de 3 permutaciones y 4 permutaciones son iguales?

Calcular el valor de\(P(n,r)\) es fácil. Queremos organizar\(r\) los objetos en una secuencia. Estos\(r\) objetos deben ser seleccionados de un grupo de\(n\) elementos. De ahí que haya\(n\) formas de llenar el primer puesto. Una vez que nos conformamos con la primera posición, lo que pongamos ahí no se puede volver a utilizar. Nos quedan\(n-1\) opciones para la segunda posición. De igual manera, una vez que se llena, sólo hay\(n-2\) opciones para el tercer puesto. Ahora bien está claro que\(P(n,r)\) es producto de\(r\) números de la forma\(n\),\(n-1, n-2, \ldots\,\). ¿Cuál es el último número de esta lista? Antes hay\(r-1\) números, por lo que debe ser\(n-(r-1)=n-r+1\).

Teorema\(\PageIndex{1}\)

Para todos los enteros\(n\) y\(r\) satisfactorios\(1 \leq r \leq n\),\[P(n,r) = n(n-1)\cdots(n-r+1) = \frac{n!}{(n-r)!}. \nonumber\]

Aunque la fórmula\(P(n,r) = \frac{n!}{(n-r)!}\) es bastante fácil de recordar, la otra forma en realidad\[P(n,r) = \underbrace{n(n-1)\cdots(n-r+1)}_r \nonumber\] es más útil en la computación numérica, especialmente cuando se hace a mano. Multiplicamos\(n\) por el siguiente entero menor\(n-1\), y luego el siguiente entero más pequeño\(n-2\), y así sucesivamente, hasta que tengamos un producto de factores\(r\) consecutivos. Por ejemplo,\[P(4,2) = 4\cdot3 = 12, \qquad\mbox{and}\qquad P(9,3) = 9\cdot 8\cdot 7 = 504. \nonumber\] ¿qué tal\(P(n,1)\) y\(P(n,2)\)?

Ejemplo\(\PageIndex{2}\label{eg:perm-02}\)

¿Cómo computarías el valor\(P(278,3)\) de a mano, o si tu calculadora no tiene ese\(_nP_r\) botón?

Solución

Nos encontramos\(P(278,3) = 278\cdot277\cdot276 = 21253656\).

Ejercicio práctico\(\PageIndex{1}\label{he:perm-01}\)

Calcular\(P(21,4)\) a mano.

Comentario

De la primera versión de la fórmula se desprende que\(P(n,n)=n!\). La segunda versión reduce a\[n! = P(n,n) = \frac{n!}{0!}. \nonumber\] Consecuentemente, para hacer que la segunda versión funcione, tenemos que definir\(0!=1\).

Comentario

En tus tareas, cuestionarios, exámenes y exámenes finales, está perfectamente bien usar la notación\(P(n,r)\) en tus respuestas. De hecho, dejar las respuestas en términos de\(P(n,r)\) da a otros una pista de cómo obtuviste la respuesta.

A menudo es más fácil y menos confuso si usamos el principio de multiplicación. Una vez que te das cuenta de que la respuesta implica\(P(n,r)\), no es difícil averiguar los valores de\(n\) y\(r\). Un buen comienzo, antes de saltar a cualquier cálculo, es preguntarse, ¿cómo enumeraría los posibles arreglos? También, intente construir algunos ejemplos. Estos pueden darte una idea de cuántas opciones tienes en cada posición.

Ejemplo\(\PageIndex{3}\label{eg:perm-03}\)

Una comisaría cuenta con 12 policías de guardia. De cuántas formas se les puede asignar a patrulla a pie en cinco distritos diferentes, suponiendo que asignemos solo un policía por distrito.

Solución

Imagina que eres el oficial que programa las asignaciones. Hay que asignar a alguien al primer distrito, y luego otro oficial al segundo distrito, y así sucesivamente.

\[ \begin{array}{cccccc} \text{district:} & \text{first} & \text{second} & \text{third} & \text{fourth} & \text{fifth} \\ \text{choices:} & \text{any officer} & \text{another officer} & \text{another different officer} & \cdots & \cdots \\ & - & - & - & - & - \\ \text{# of choices:} & 12 & 11 & 10 & 9 & 8 \end{array} \nonumber\]

Hay 12 opciones para el primer distrito, 11 para el segundo, etc. El principio de multiplicación implica que la respuesta es\(12\cdot11\cdots\), que es en la forma de\(P(n,r)\). Ya que el producto inicia con 12, y necesitamos un producto de 5 números consecutivos, la respuesta es\(P(12,5)\).

Ejercicio práctico\(\PageIndex{2}\label{he:perm-02}\)

Una escuela envía a un equipo de seis corredores a un juego de relevos. ¿De cuántas formas pueden ser seleccionados para participar en el relevo\(4 \times 100\) m?

Ejemplo\(\PageIndex{4}\label{eg:perm-04}\)

De una colección de 10 banderas de diferentes patrones, ¿cuántas señales de tres banderas podemos poner en un poste?

Solución

Dado que las banderas están dispuestas en un asta de bandera, el orden es importante. Hay 10 opciones para la bandera superior, 9 para la segunda y 8 para la tercera. Por lo tanto, se pueden formar\(10\cdot9\cdot8 = P(10,3)\) diferentes señales.

Ejemplo\(\PageIndex{5}\label{eg:perm-05}\)

Determine el número de funciones\(f:{\{1,3,4,7,9\}}\to{\mathbb{Z}_{22}}\) si

1. No hay restricciones.
2. \(f\)es uno a uno.
3. \(f\)está en.

Solución

Para distinguir una función de otra, tenemos que comparar sus imágenes. De ahí que una función esté completamente determinada por sus imágenes (sorpresa: ¡no por su fórmula!). Después de todo, puede que ni siquiera sepamos la fórmula detrás de una función, así que no podemos y no debemos confiar solo en la fórmula.

Para determinar cuántas funciones hay de\(\{1,3,4,7,9\}\) a\(\mathbb{Z}_{22}\), tenemos que determinar el número de formas de asignar valores a\(f(1)\),\(f(3)\),\(f(4)\),\(f(7)\) y\(f(9)\).

\[ \begin{array}{cccccc} \text{images:} & f(1) & f(3) & f(4) & f(7) & f(9) \\ \text{choices:} \\ & - & - & - & - & - \\ \text{# of choices:} \end{array} \nonumber\]

1. Si no hay restricciones, tenemos 22 opciones para cada una de estas cinco imágenes. De ahí que haya\(22\cdot22\cdot22\cdot22\cdot22 = 22^5\) funciones.
2. Si\(f\) es uno a uno, no podemos duplicar las imágenes. Entonces tenemos 22 opciones para\(f(1)\), 21 para\(f(3)\), y así sucesivamente. Hay funciones\(P(22,5)\) uno a uno.
3. Hay como máximo cinco imágenes distintas, pero\(\mathbb{Z}_{22}\) tiene 22 elementos, por lo que al menos 17 de ellas quedarán sin usar. De ahí\(f\) que nunca pueda estar en. Por lo tanto, el número de funciones on es cero.

Ejercicio práctico\(\PageIndex{3}\label{he:perm-03}\)

¿Cuántas funciones hay de\(\{2,4,6,8,10\}\) a\(\mathbb{Z}_{15}\)? ¿Cuántos de ellos son uno a uno?

Ejemplo\(\PageIndex{6}\label{eg:perm-06}\)

Dejar\(A\) y\(B\) ser conjuntos finitos, con\(|A|=s\) y\(|B|=t\). Determine el número de funciones uno a uno de\(A\) a\(B\).

Solución

¿Cómo podemos llegar a una función uno a uno de\(A\) a\(B\)? Tenemos que especificar la imagen de cada elemento en\(A\). Hay\(t\) opciones para el primer elemento. Como no se permiten imágenes repetidas, solo tenemos\(t-1\) opciones para la imagen del segundo elemento en\(A\), y\(t-2\) opciones para la tercera imagen, y así sucesivamente. La respuesta es\(P(t,s)\).

¿Y si\(t<s\)? Sabemos que en tal evento, no existe ninguna función uno-a-uno de\(A\) a\(B\) porque no hay suficientes imágenes distintas. ¿\(P(t,s)\)Todavía tiene sentido? La versión del producto de la fórmula dice que\(P(t,s)\) es un producto de números\(s\) consecutivos. De ahí, por ejemplo,\[P(3,6) = 3\cdot2\cdot1\cdot0\cdot(-1)\cdot(-2) = 0, \nonumber\] lo que significa que no hay una función uno-a-uno de\(A\) a\(B\).

No todos los problemas usan\(P(n,r)\). En muchas situaciones, tenemos que usar\(P(n,r)\) junto con otros números. El enfoque más seguro es confiar en los principios de suma y multiplicación.

Ejemplo\(\PageIndex{7}\label{eg:perm-07}\)

¿Cuántos enteros de cuatro dígitos hay que no contienen dígitos repetidos?

Solución

Hay 10 opciones para cada dígito, pero la respuesta no lo es\(P(10,4)\), porque no podemos usar 0 como primer dígito. Para asegurar que tenemos un entero de cuatro dígitos, el primer dígito debe ser distinto de cero. Esto nos deja 9 opciones para el primer dígito. Entonces tenemos 9 opciones para el segundo dígito, 8 y 7 para los dos siguientes. La respuesta es\(9\cdot9\cdot8\cdot7\).

Ejemplo\(\PageIndex{8}\label{eg:perm-08}\)

Doce niños están jugando “sillas musicales”, con 9 sillas dispuestas en círculo en el piso. ¿De cuántas maneras se pueden sentar?

Solución

La respuesta no es\(P(12,9)\) porque cualquier posición pueda ser la primera posición en una permutación circular. Lo que importa es la colocación relativa de los objetos seleccionados, lo único que nos importa es quién está sentado junto a quién. La respuesta correcta se puede encontrar en el siguiente teorema.

Teorema\(\PageIndex{1}\label{thm:circperm}\)

El número de\(r\) permutaciones circulares de un conjunto\(n\) de elementos es\(P(n,r)/r\).

Prueba

Compare el número\(r\) de permutaciones circulares con el número\(r\) de permutaciones lineales. Empezar en cualquier posición en una\(r\) permutación circular, e ir en el sentido de las agujas del reloj; obtenemos una\(r\) permutación lineal. Dado que podemos comenzar en cualquiera de las\(r\) posiciones, cada\(r\) permutación circular produce\(r\) permutaciones\(r\) lineales. Esto significa que hay\(r\) veces tantas\(r\) permutaciones circulares como\(r\) permutaciones lineales. Por lo tanto, el número\(r\) de permutaciones circulares es\(P(n,r)/r\).

Prueba alternativa

Dejar\(A\) ser el conjunto de todas las\(r\) permutaciones lineales de los\(n\) objetos, y dejar\(B\) ser el conjunto de todas las\(r\) permutaciones circulares. Defina una función de\(A\) a de la\(B\) siguiente manera. Ante cualquier\(r\) -permutación, formar su imagen uniendo su “cabeza” a su “cola”. Queda claro, usando el mismo argumento en la prueba anterior, que\(f\) es una función\(r\) -a-uno, lo que significa\(f\) mapea\(r\) distintos elementos de\(A\) a la misma imagen en\(B\). Por lo tanto\(A\) tiene\(r\) veces tantos elementos como en\(B\). Esto significa\(|A| = r\cdot|B|\). Ya que\(|A|=P(n,r)\), encontramos\(|B|=P(n,r)/r\).

Ejercicio práctico\(\PageIndex{4}\label{he:perm-04}\)

Un cartón circular tiene ocho puntos marcados a lo largo de su borde. ¿De cuántas maneras podemos pegar ocho cuentas de diferentes colores, una en cada punto?

Ejercicio práctico\(\PageIndex{5}\label{he:perm-05}\)

¿De cuántas maneras podemos formar un collar con ocho cuentas de diferente color?

Comentario: Cuando se da la vuelta a un collar, sigue siendo el mismo collar. Así, la orientación del collar no importa: podemos contar las cuentas en sentido horario, o en sentido contrario a las agujas del reloj.

Ejemplo\(\PageIndex{9}\label{eg:perm-09}\)

¿De cuántas maneras podemos organizar 20 caballeros en una mesa redonda? ¿Y si dos de ellos se niegan a sentarse uno al lado del otro?

Solución

Sin restricción alguna, hay\(20!/20 = 19!\) formas de asentar a los 20 caballeros. Para resolver el segundo problema, use complemento. Si dos de ellos siempre se sientan juntos, en efecto estamos arreglando 19 objetos en círculo. Entre ellos, estos dos caballeros se pueden sentar de dos maneras, dependiendo de quién esté sentado a la izquierda. De ahí que haya\(2\cdot 19!/19=2\cdot18!\) formas de asentar a los 20 caballeros, con dos de ellos siempre juntos. Por lo tanto, la respuesta final al segundo problema es\(19!-2\cdot18!\).

Resumen y revisión

• Usar permutación si el orden importa: las palabras clave arreglo, secuencia y orden sugieren que debemos usar permutación.
• A menudo es más efectivo usar el principio de multiplicación directamente.
• El número de formas de organizar\(n\) los objetos linealmente es\(n!\), y el número de formas de organizarlos en un círculo es\((n-1)!\).

Ejercicio\(\PageIndex{1}\label{ex:perm-01}\)

¿Cuántas contraseñas de ocho caracteres se pueden formar con las 26 letras del alfabeto inglés, cada una de las cuales puede estar en mayúscula o minúscula, y los 10 dígitos? ¿Cuántos de ellos no tienen carácter repetido?

Ejercicio\(\PageIndex{2}\label{ex:perm-02}\)

¿Cuántas funciones hay de\(\mathbb{Z}_6\) a\(\mathbb{Z}_{12}\)? ¿Cuántos de ellos son uno a uno?

Ejercicio\(\PageIndex{3}\label{ex:perm-03}\)

La junta escolar de un distrito escolar cuenta con 14 integrantes. ¿De cuántas maneras pueden ser seleccionados el presidente, el primer vicepresidente, el segundo vicepresidente, el tesorero y el secretario?

Ejercicio\(\PageIndex{4}\label{ex:perm-04}\)

Los equipos de lucha libre de dos escuelas cuentan con ocho y 10 integrantes respectivamente. ¿De cuántas formas se pueden conformar tres partidos entre ellos?

Ejercicio\(\PageIndex{5}\label{ex:perm-05}\)

Los equipos de lucha libre de tres escuelas cuentan con siete, 10 y 11 integrantes, respectivamente. Cada escuela tendrá tres partidos contra cada una de las otras dos escuelas. ¿De cuántas maneras se pueden arreglar estos partidos?

Ejercicio\(\PageIndex{6}\label{ex:perm-06}\)

Una maestra lleva a almorzar su clase de cálculo AP de 8 alumnos. Se sientan alrededor de una mesa de comedor circular.

1. ¿Cuántos arreglos de asientos son posibles?
2. ¿Cuántos arreglos de asientos hay si el maestro tiene que sentarse en la silla más cercana a la fuente de refrescos?
3. Entre los alumnos se encuentran un conjunto de trillizos. ¿Cuántos asientos hay sin que los tres estén sentados juntos?

Ejercicio\(\PageIndex{7}\label{ex:perm-07}\)

Once alumnos van a comer. Hay dos mesas circulares en el comedor, una tiene capacidad para 7 personas, la otra puede albergar 4. ¿De cuántas maneras se pueden sentar?

Ejercicio\(\PageIndex{8}\label{ex:perm-08}\)

Cinco parejas asisten a un banquete de bodas. Están sentados en una mesa larga. ¿Cuántos arreglos de asientos alternan hombres y mujeres? ¿Y si la mesa es de forma circular?