2.2: Permutaciones
- Page ID
- 118280
En la sección anterior, consideramos cadenas en las que se permite la repetición de símbolos. Por ejemplo, “01110000” es una cadena de bits perfectamente buena de longitud ocho. Sin embargo, en muchos ajustes aplicados donde una cadena es un modelo apropiado, se puede usar un símbolo como máximo en una posición.
Imagínese colocar las 26 letras del alfabeto inglés en una bolsa y sacarlas una a la vez (sin devolver una letra una vez dibujada) para formar una cadena de seis caracteres. Sabemos que hay\(26^6\) cadenas de longitud seis que se pueden formar a partir del alfabeto inglés. Sin embargo, si restringimos la forma de formación de cuerdas, no todas las cadenas son posibles. La cadena “amarilla” tiene seis caracteres, pero usa la letra “l” dos veces y así no se puede formar dibujando letras de una bolsa. Sin embargo, la “chaqueta” se puede formar de esta manera. A partir de una bolsa llena, observamos que hay 26 opciones para la primera letra. Una vez que se ha retirado, quedan 25 letras en la bolsa. Después de dibujar la segunda letra, quedan 24 letras restantes. Continuando, observamos que inmediatamente antes de sacar la sexta letra de la bolsa, hay 21 letras en la bolsa. Así, podemos formar cadenas de\(26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 \cdot 21\) seis caracteres de letras inglesas dibujando letras de una bolsa, un poco más de la mitad del número total de cadenas de seis caracteres en este alfabeto.
Para generalizar el ejemplo anterior, ahora introducimos permutaciones. Para ello, let\(X\) be a finite set and let\(n\) be a positive integer. Una\(X\) cadena\(s=x_1x_2...x_n\) -se llama permutación si todos los\(n\) caracteres utilizados en\(s\) son distintos. Claramente, la existencia de una\(X\) -permutación de longitud lo\(n\) requiere\(|X| \geq n\).
Cuando\(n\) es un entero positivo, definimos\(n!\) (léase “\(n\)factorial”) por
\(n! = n \cdot (n-1) \cdot (n-2) \cdot \cdot \cdot \cdot 3 \cdot 2 \cdot 1\)
Por convención, nos fijamos\(0! = 1\). A modo de ejemplo,\(7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5040\).
Ahora para enteros\(m,n\) con\(m \geq n \geq 0\) definir\(P(m,n)\) por
\(P(m,n) = \frac{m!}{(m-n)!} = m(m-1) \cdot \cdot \cdot (m-n+1)\).
Por ejemplo,\(P(9,3) = 9 \cdot 8 \cdot 7 = 504\) y\(P(8,4) = 8 \cdot 7 \cdot 6 \cdot 5 = 1680\). Además, un sistema de álgebra computacional reportará rápidamente que
\(P(68,23) = 207 322 312 233 755 157 418 942 861 642 039 296 000 00\).
Si\(X\) es un conjunto de\(m\) elementos -y\(n\) es un entero positivo con\(m \geq n \), entonces el número de\(X\) -cadenas de longitud\(n\) que son permutaciones es\(P(m,n)\).
- Prueba
-
La proposición es cierta ya que al construir una permutación\(s = x_1x_2,...,x_n\) a partir de un conjunto\(m\) -element, vemos que hay\(m\) opciones para\(x_1\). Después de arreglar\(x_1\), tenemos eso para\(x_2\), hay\(m-1\) opciones, ya que podemos usar cualquier elemento de\(X - \{x_1\}\). Para\(x_3\), hay\(m-2\) opciones, ya que podemos usar cualquier elemento en\(X - \{x_1,x_2\}\). Porque\(x_n\), hay\(m-n+1\) opciones, porque podemos usar cualquier elemento de\(X\) excepción\(x_1,x_2,...x_{n-1}\). Señalando que
\(P(m,n) = \frac{m!}{(m-n)!} = m(m-1)(m-2)...(m-n+1)\),
nuestra prueba está completa.
Tenga en cuenta que la respuesta a la que llegamos en el Ejemplo 2.5 es simplemente\(P(26,6)\) como esperaríamos a la luz de la Proposición 2.6.
Es momento de elegir una pizarra de cuatro oficiales de clase (Presidente, Vicepresidente, Secretario y Tesorero) del grupo de 80 alumnos matriculados en Combinatoria Aplicada. Si algún estudiante interesado pudiera ser elegido para algún cargo (Alice sostiene que este es un gran “si” ya que Bob se postula), ¿cuántas pizarras diferentes de oficiales pueden ser elegidas?
- Solución
-
Para contar posibles pizarras de oficiales, trabaja a partir de un conjunto\(X\) que contiene los nombres de los 80 estudiantes interesados (sí, incluso pobre Bob). Una permutación de longitud cuatro elegida\(X\) es entonces una pizarra de oficiales al considerar el primer nombre en la permutación como Presidente, el segundo como Vicepresidente, el tercero como Secretario y el cuarto como Tesorero. Así, el número de pizarras de oficiales es\(P(80,4) = 379 579 20\).
Volvamos a la pregunta de matrícula del Ejemplo 2.1. Supongamos que Georgia requirió que las tres letras fueran distintas entre sí. Entonces, en lugar de tener\(26^3 = 17 576\) formas de cubrir los tres últimos puestos en la placa, tendríamos\(P(26,3) = 26 \times 25 \times 24 = 15 600\) opciones, dando un total de\(140 400 000\) placas.
Como otro ejemplo, supongamos que se permitió la repetición de letras pero los tres dígitos en las posiciones dos a cuatro deben ser todos distintos entre sí (pero podrían repetir el primer dígito, que aún debe ser distinto de cero). Entonces aún quedan 9 opciones para la primera posición y\(26^3\) opciones para las letras, pero los tres dígitos restantes se pueden completar de\(P(10,3)\) maneras. El número total de placas sería entonces\(9 \times P(10,3) \times 26^3\). Si queremos prohibir también la repetición del dígito en la primera posición, necesitamos un poco más de reflexión. Primero tenemos 9 opciones para ese dígito inicial. Entonces, al rellenar las siguientes tres posiciones con dígitos, necesitamos una permutación de longitud 3 elegida entre los 9 dígitos restantes. Así, hay\(9 \times P(9,3)\) formas de completar la porción de dígitos, dando un total de\(9 \times P(9,3) \times 26^3\) placas.