6.2: Permutaciones

Última actualización
Guardar como PDF

Page ID: 117508

$ \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}}$

Cuando contamos las cosas, a menudo nos encontramos con permutaciones. Una permutación de$n$ distintos objetos es una disposición de ellos en una secuencia. Por ejemplo, supongamos que los tres niños Davies necesitan cepillarse los dientes, pero solo uno de ellos puede usar el fregadero a la vez. ¿En qué orden van a cepillarse? Una posibilidad es Lizzy, luego T.J., luego Johnny. Otra posibilidad es T.J., luego Lizzy, luego Johnny. Otro es Johnny, luego Lizzy, luego T.J. Estas son todas diferentes permutaciones de los chicos Davies. Resulta que hay seis de ellos (¡encuentra los 6 por ti mismo!)

Contar el número de permutaciones es solo una aplicación especial del Teorema Fundamental del Conteo. Para el ejemplo de cepillarse los dientes, tenemos$n=3$ diferentes “partes” al problema, cada una de las cuales tiene$n_i$ opciones para asignarle. Hay tres niños Davies diferentes que podrían cepillarse los dientes primero, entonces$n_1=3$. Una vez que se elige a ese niño, quedan dos niños restantes que podrían cepillarse en segundo lugar, entonces$n_2=2$. Entonces, una vez que hemos seleccionado un primer cepillador y un segundo cepillador, solo queda una opción para el tercer cepillador, entonces$n_3=1$. Esto significa que el número total de órdenes de cepillado posibles es:\[3 \times 2 \times 1 = 6.\]

Este patrón surge tanto que los matemáticos han establecido una notación especial para ello:\[n \times (n-1) \times (n-2) \times \cdots \times 1 = n!\ \text{(``$n$-factorial")}\]

Decimos que hay “3-factoriales” diferentes órdenes de cepillado para los niños Davies. Para nuestros fines la noción de factorial sólo se aplicará para enteros, así que ¡no hay tal cosa como 23.46! o$\pi$!. (En aplicaciones avanzadas de informática, sin embargo, los matemáticos a veces definen factorial para los no enteros). También definimos 0! ser 1, lo que podría sorprenderte.

Esto surge muchísimo. Si te doy un conjunto desordenado de letras para desaleatorizar, como “KRIBS" (piensa en el juego de palabras Jump en el periódico), ¿cuántos descodificadores diferentes hay? ¡La respuesta es 5! , o 120, uno de los cuales es BRISK. Digamos que barajo una baraja de cartas antes de jugar a la guerra. ¹ ¿Cuántos juegos diferentes de Guerra hay? ¡La respuesta es 52! , ya que cualquiera de las cartas de la baraja podría ser barajada en la parte superior, entonces cualquiera que no sea esa carta superior podría ser segunda, entonces cualquiera excepto esas dos podría ser tercera, etc. Diez paquetes llegan casi simultáneamente a un enrutador de red. ¿De cuántas formas se pueden poner en cola para su transmisión? ¡10! formas, al igual que una familia Davies más grande.

La función factorial crece realmente, muy rápido, por cierto, incluso más rápido que las funciones exponenciales. Una palabra de cinco letras como “BRISK" tiene 120 permutaciones, pero “AMBIDEGROSAMENTE" tiene 87,178,291,200, diez veces la población de la tierra. El número de formas de barajar una baraja es

80,658,175,170,944,942,408,940,349,866,698,506,766,127,860,028,660,283,290,685,487,972,352

así que no creo que mis chicos terminen jugando el mismo juego de Guerra dos veces en el corto plazo, ni mi esposa y yo la misma mano de puente.

Enumerar permutaciones

Hemos descubierto que hay 120 permutaciones de BRISK, pero ¿cómo haríamos para enumerarlas todas? Puedes jugar con los niños Davies y tropezar con las 6 permutaciones, pero para números más grandes es más difícil. Necesitamos una manera sistemática.

Dos de las formas más fáciles de enumerar permutaciones implican la recursión. Aquí hay uno:

Algoritmo #1 para enumerar permutaciones

Comience con un conjunto de$n$ objetos.
1. Si$n=1$, sólo hay una permutación; es decir, el objeto mismo.
2. De lo contrario, elimina uno de los objetos, y encuentra las permutaciones de los$n-1$ objetos restantes. Después, inserte el objeto eliminado en cada posición posible, creando otra permutación cada vez.

Como siempre con la recursión, resolver un problema mayor depende de resolver problemas más pequeños. Empecemos con RIESGO. Ya hemos descubierto por el ejemplo del cepillado de dientes que las permutaciones de ISK son ISK, IKS, SIK, SKI, KIS y KSI. Entonces, para encontrar las permutaciones de RIESGO, insertamos una R en cada ubicación posible para cada una de estas permutaciones ISK. Esto nos da:

R ISK I R SK ES R K ISK R R IKS I R KS IK R S
IKS R R SIK $\cdots$

y así sucesivamente. Una vez que tenemos las permutaciones RIESGO, podemos generar las permutaciones BRISK de la misma manera:

B RIESGO R B ISK RI B SK RIS B K RIESGO B B IRSK I B RSK
IR B SK IRS B K IRSK B B RSIK $\cdots$

Otro algoritmo para lograr el mismo objetivo (aunque en un orden diferente) es el siguiente:

Algoritmo #2 para enumerar permutaciones

Comience con un conjunto de$n$ objetos.
1. Si$n=1$, sólo hay una permutación; es decir, el objeto mismo.
2. De lo contrario, eliminar cada uno de los objetos a su vez, y anteponer ese objeto a las permutaciones de todos los demás, creando otra permutación cada vez.

Este me parece un poco más fácil de entender, pero al final es preferencia personal. Las permutaciones de BRISK son: “B seguido de todas las permutaciones de RIESGO, más R seguido de todas las permutaciones de BISK, más I seguido de todas las permutaciones de BRSK, etc." Así que las primeras permutaciones de una palabra de 4 letras son:

R ISKR IKS R SIK R ESQUÍ R KIS R KSI I RSK I RKS I SRK I SKR I KRS I KSR S RIK $\cdots$

Entonces, para la palabra de 5 letras:

B RIKS B RIKS B RSIK B RSKI B RKIS B RKSI
B IRSK B IRKS $\cdots$

Permutaciones parciales

A veces queremos contar las permutaciones de un conjunto, pero solo queremos elegir algunos de los elementos cada vez, no todos ellos. Por ejemplo, consideremos un torneo de golf en el que los diez primeros finalistas (de 45) reciben todos premios en efectivo, siendo el ganador del primer lugar el que más recibe, el segundo finalista un monto menor, y así sucesivamente bajando al décimo lugar, quien recibe un premio nominal. ¿Cuántos acabados diferentes son posibles para el torneo?

En este caso, queremos saber cuántos ordenamientos diferentes de golfistas hay, pero resulta que pasado el décimo lugar, no nos importa en qué orden terminaron. Todo lo que importa son los primeros diez lugares. Si los diez primeros son 1.Tiger, 2.Phil, 3.Lee, 4.Rory$\dots$,, y 10.Bubba, entonces no importa si Jason terminó$11^{\text{th}}$ o$45^{\text{th}}$.

Es fácil ver que hay 45 posibles ganadores, luego por cada ganador hay 44 posibles segundos colocadores, etc., por lo que este total resulta ser:\[45 \times 44 \times 43 \times 42 \times 41 \times 40 \times 39 \times 38 \times 37 \times 36 = \text{11,576,551,623,436,800 finishes}.\] Cada uno de los acabados se llama una permutación parcial. Es una permutación de$k$ ítems elegidos del$n$ total, y se denota$p_{n,k}$. El número de tales permutaciones funciona para\[n \times (n-1) \times (n-2) \times \cdots \times (n-k+1).\] El “$n-k+1$" bit puede ser confuso, así que tómate tu tiempo y piénsalo bien. Para el caso del torneo de golf, nuestro término más alto fue 45 y nuestro término más bajo fue 36. Esto es porque$n$ era 45 y$k$ era 10, y así solo queríamos llevar a cabo la multiplicación a 36 (no 35), y 36 es 45-10+1.

Esto se puede expresar de manera más compacta de algunas maneras diferentes. Primero, podemos usar factoriales para representarlo:\[\begin{aligned} n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) &= \\ \dfrac{n \times (n-1) \times (n-2) \times \cdots \times 1}{(n-k) \times (n-k-1) \times (n-k-2) \times \cdots \times 1} &= \dfrac{n!}{(n-k)!}.\end{aligned}\] También, podríamos usar nuestra notación compacta de producto:\[\begin{aligned} n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) &= \prod_{i=0}^{k-1}{(n-i)}.\end{aligned}\] Finalmente, al igual que con las permutaciones (no parciales), esto surge tanto que los profesionales han inventado una notación especial para ello. Parece un poder, pero tiene un subrayado bajo el exponente:\[\begin{aligned} n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) &= n^{\underline{k}}.\end{aligned}\] Esto se pronuncia “$n$$k$a-a-la-caída”, y fue inventado por uno de los informáticos más brillantes de la historia, Donald Knuth.

Para mantener recto lo que$n^{\underline{k}}$ significa, piense en ello como lo mismo que simple exponenciación, excepto que el producto disminuye en lugar de permanecer igual. Por ejemplo, “17-to-the-$6^{\text{th}}$" es\[17^6 = 17 \cdot 17 \cdot 17 \cdot 17 \cdot 17 \cdot 17\] pero “17-to-the-$6^{\text{th}}$ -falling” es\[17^{\underline{6}} = 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13 \cdot 12.\] En ambos casos, estás multiplicando el mismo número de términos, es solo que en el segundo caso, estos términos están “cayendo”.

En fin, aparte de la notación, las permutaciones parciales abundan en la práctica. Un canal de películas nocturnas podría mostrar cuatro películas clásicas consecutivas todas las noches. Si hay 500 películas en la biblioteca del estudio, ¿cuántos horarios nocturnos de televisión son posibles? Respuesta:$500^{\underline{4}}$, ya que hay 500 opciones de qué mostrar a las 7pm, luego 499 opciones para las 9pm, 498 para las 11pm y 497 para el show tardío de la 1am.

Los 41 corredores de autos más rápidos se clasificarán para la carrera del domingo, y se colocarán desde la Pole Position a la baja dependiendo de su tiempo de clasificación. Si 60 autos participan en el calor clasificatorio, entonces hay$60^{\underline{41}}$ diferentes configuraciones de inicio posibles para el domingo.

A los estudiantes de secundaria que ingresen a sexto grado se les asignará un horario semestral que consta de cinco “bloques” (periodos), cada uno de los cuales tendrá una de trece clases (ciencias, matemáticas, orquesta, sala de estudios, etc.) ¿Cuántos horarios son posibles? Lo adivinaste,$13^{\underline{5}}$. Observe que esta es la respuesta correcta solo porque no se permiten repeticiones: no queremos programar a ningún estudiante para Historia Americana más de una vez. Si un estudiante pudiera tomar la misma clase más de una vez al día, entonces habría$13^5$ (no “cayendo”) diferentes horarios posibles.

“Guerra” es un juego de cartas sin sentido que no implica estrategia ni toma de decisiones por parte de los jugadores. Una vez que barajas el mazo inicial, se fija todo el resultado del juego.