3.1: Permutaciones
- Page ID
- 114576
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
Comenzamos por mirar las permutaciones, porque estas son una aplicación sencilla de la regla del producto. La palabra “permutación” significa un reordenamiento, y esto es exactamente lo que es una permutación: un orden de varios elementos distintos en una línea. A veces, aunque tenemos una gran cantidad de elementos distintos, queremos señalar un número menor y organizarlos en una línea; esto también es una especie de permutación.
Definición: Permutación
Una permutación de objetos\(n\) distintos es una disposición de esos objetos en una línea ordenada. Si\(1 ≤ r ≤ n\) (y\(r\) es un número natural) entonces una permutación r de\(n\) objetos es una disposición\(r\) de los\(n\) objetos en una línea ordenada.
Por lo que una permutación implica elegir elementos de una población finita en la que cada ítem se identifica de manera única, y realizar un seguimiento del orden en que se eligieron los artículos.
Ya que estamos estudiando la enumeración, no debería sorprenderte que lo que vamos a estar preguntando en esta situación es cuántas permutaciones hay, en diversas circunstancias. Comencemos con un ejemplo en el que calcularemos el número de\(3\) -permutaciones de diez objetos (o en este caso, personas).
Ejemplo\(\PageIndex{1}\)
Diez deportistas compiten por medallas olímpicas en patinaje de velocidad femenino (1000 metros). ¿De cuántas maneras podrían terminar siendo otorgadas las medallas?
Solución
Hay tres medallas: oro, plata y bronce, por lo que esta pregunta equivale a encontrar el número de\(3\) -permutaciones de los diez atletas (la primera persona en la\(3\) -permutación es la que obtiene la medalla de oro, la segunda obtiene la plata y la tercera obtiene el bronce).
Para resolver esta pregunta, aplicaremos la regla del producto, donde los aspectos que pueden variar son los ganadores de las medallas de oro, plata y bronce. Comenzamos por considerar cuántos atletas diferentes podrían obtener la medalla de oro. La respuesta es que cualquiera de los diez atletas podría conseguir esa medalla. No importa cuál de los atletas obtenga la medalla de oro, una vez que se decida eso trasladamos nuestra consideración a la medalla de plata. Dado que a uno de los atletas ya se le otorgó la medalla de oro, sólo nueve de ellos permanecen en la contienda por la medalla de plata, por lo que para cualquier elección de atleta que gane el oro, el número de opciones para quien obtiene la medalla de plata es de nueve. Por último, con los medallistas de oro y plata fuera de contienda por el bronce, quedan ocho opciones para quién podría ganar esa medalla. Así, el número total de formas en que se podrían otorgar las medallas es\(10 · 9 · 8 = 720\).
Podemos usar el mismo razonamiento para determinar una fórmula general para el número\(r\) de permutaciones de\(n\) objetos:
Teorema\(\PageIndex{1}\)
El número\(r\) de permutaciones de\(n\) objetos es\(n(n − 1). . .(n − r + 1)\)
- Prueba
-
Hay\(n\) formas en las que se puede elegir el primer objeto (cualquiera de los\(n\) objetos). Para cada una de estas posibles elecciones, quedan\(n-1\) objetos a elegir para el segundo objeto, etc.
Nota
Usamos\(n!\) para denotar el número de permutaciones de\(n\) objetos, por lo que
\[n! = n(n − 1). . . 1\].
Por convención, definimos\(0! = 1\).
Definición: Factorial
Leemos\(n!\) como “\(n\)factorial”, así lo es\(n\) factorial\(n(n − 1). . . 1\). Por lo tanto, el número de permutaciones r de\(n\) objetos se puede reescribir como\(\dfrac{n!}{(n − r)!}\). Cuando\(n = r\) esto da\(\dfrac{n!}{0!} = n!\), dando sentido a nuestra definición que\(0! = 1\).
Ejemplo\(\PageIndex{2}\)
Hay 36 personas en un taller. Están sentados en seis mesas redondas de seis personas cada una para el almuerzo. La familia Morris (de tres) ha pedido sentarse juntos (lado a lado). ¿Cuántos arreglos de asientos diferentes son posibles en la mesa de la familia Morris?
Solución
Primero, hay\(3! = 6\) formas de arreglar el orden en que los tres miembros de la familia Morris se sientan a la mesa. Dado que las mesas son redondas, no importa qué asientos específicos tomen, solo importa el orden en que se sientan. Una vez que la familia Morris está sentada, las tres sillas restantes están determinadas de manera única por sus posiciones relativas a la familia Morris (una a su derecha, una a su izquierda y otra frente a ellas). Hay otras 33 personas en la conferencia; tenemos que elegir a tres de estas personas y ponerlas en orden en las tres sillas vacantes. Hay\(\dfrac{33!}{(33 − 3)!} = \dfrac{33!}{30!}\) formas de hacer esto. En total, hay\(6 \left( \dfrac{33!}{30!} \right) = 196,416\) diferentes arreglos de asientos posibles en la mesa de la familia Morris.
Al ajustar los detalles del ejemplo anterior, puede requerir algunos procesos de pensamiento bastante diferentes para encontrar la respuesta.
Ejemplo\(\PageIndex{3}\)
En el mismo taller, hay tres mesas redondas, con capacidad para doce personas cada una. Los miembros de la familia Morris (Joy, Dave y Harmony) todavía quieren sentarse en la misma mesa, pero han decidido extenderse (así que no hay dos de ellos uno al lado del otro) para conocer a más gente. ¿Cuántos arreglos de asientos diferentes son posibles ahora en la mesa de la familia Morris?
Solución
Comencemos colocando arbitrariamente a Joy en algún lugar de la mesa, y sentando a todos los demás relativos a ella. Esto distingue efectivamente a los otros once escaños. A continuación, consideraremos a las nueve personas que no están en la familia de Joy, y las colocaremos (de pie) en un orden en sentido horario alrededor de la mesa de ella. Hay\(\dfrac{33!}{(33 − 9)!}\) formas de hacerlo. Antes de asignar asientos a estas nueve personas, decidimos dónde colocar a Dave y Harmony entre ellos.
(En el diagrama anterior, los dígitos\(9\) representan\(1\) a las otras nueve personas que están sentadas en la mesa de la familia Morris, y el\(J\) representa la posición de Joy). Dave puede sentarse entre cualquier par de no morrenses que estén parados uno al lado del otro; es decir, en cualquiera de los puntos marcados por pequeños puntos negros en el diagrama anterior. Así, hay ocho opciones posibles para dónde se sentará Dave. Ahora Harmony puede entrar en cualquiera de los siete puntos restantes marcados por puntos negros. Una vez que Dave y Harmony están en su lugar, todos se desplazan para igualar el círculo (así desaparecen los puntos negros restantes), y toman sus asientos en el orden determinado.
Hemos demostrado que hay\(\dfrac{33!}{24!} · 8 · 7\) posibles arreglos de asientos en la mesa de Morris. Ese es un número realmente grande, y es bastante aceptable dejarlo en este formato. No obstante, en caso de que encuentres otra forma de resolver el problema y quieras verificar tu respuesta, el número total es\(783\),\(732\),\(837\),\(888\),\(000\).
Ejercicio\(\PageIndex{1}\)
Usa lo que has aprendido sobre las permutaciones para resolver los siguientes problemas. También se puede requerir la regla de suma y/o producto.
- Seis personas, todas las cuales pueden tocar tanto el bajo como la guitarra, están audicionando para una banda. Hay dos espacios disponibles: guitarra principal y bajista. ¿De cuántas maneras se puede completar la banda?
- Tu amigo Garth prueba para una obra de teatro. Después de las audiciones, te manda un mensaje de texto que consiguió una de las partes que quería, y que (incluido él) nueve personas probaron para los cinco papeles. Sabes que hubo dos partes que le interesaron. ¿De cuántas maneras podría completarse el elenco (quién obtiene qué papel importa)?
- Estás creando una contraseña\(8\) -character. Se le permite usar cualquiera de los caracteres en\(26\) minúscula, y debe usar exactamente un dígito (de\(0\) a través\(9\)) en algún lugar de la contraseña. No se te permite usar ningún personaje más de una vez. ¿Cuántas contraseñas diferentes puedes crear?
- \(3\)¿Cuántas “palabras” de letras (cadenas de caracteres, en realidad no tienen que ser palabras) se pueden formar a partir de las letras de la palabra FUERTE? ¿Cuántas de esas palabras contienen una s? (No puede usar una carta más de una vez.)
- ¿Cuántas permutaciones de no\(\{0, 1, 2, 3, 4, 5, 6\}\) tienen dígitos pares adyacentes? Por ejemplo, una permutación como 5034216 no está permitida porque\(4\) y\(2\) son adyacentes.