Archivo de la etiqueta: coeficiente multinomial

Probabilidad I: Principios de Conteo 2 – Permutaciones

Por Octavio Daniel Ríos García

Deja un comentario

Introducción

En la entrada pasada vimos dos principios básicos de conteo: el de la suma y el del producto. En particular, el principio del producto tiene aplicaciones más especializadas. Tal es el caso de las permutaciones y las combinaciones. Dada una colección de objetos, es posible extraer una cantidad fija $k$ de ellos y formar arreglos de tamaño $k$. De estos arreglos puede o no importarnos el orden de los objetos que los forman. Esto da lugar al concepto que veremos en esta entrada: las permutaciones.

Motivación

Comenzaremos con el concepto de permutación. Dada una colección de $n$ objetos, es posible extraer $k$ (con $k \leq n$) de ellos para formar un arreglo lineal. Es decir, se acomodan los elementos en una línea. Lo que nos interesa es ver la cantidad de arreglos lineales de tamaño $k$ que pueden obtenerse de una colección de $n$ objetos. Sin embargo, en un arreglo nos importa el orden en el que se acomodan los objetos. Así, dos arreglos lineales con los mismos elementos pero ordenados de diferente manera se consideran como distintos. Por ello, si queremos la cantidad de arreglos lineales ordenados posibles, estas diferencias se toman en cuenta. Comencemos con un ejemplo.

Ejemplo. En un grupo de $10$ estudiantes, se escoge a $5$ de ellos y se sientan en una fila para una fotografía. ¿Cuántos arreglos lineales pueden formarse?

Como mencionamos anteriormente, la palabra arreglo designa una importancia al orden de los elementos. Si $\mathrm{A}$, $\mathrm{B}$, $\mathrm{C}$, …, $\mathrm{I}$, $\mathrm{J}$ denotan a los $10$ estudiantes, entonces $\mathrm{BCEFI}$, $\mathrm{CEFIB}$ y $\mathrm{ABCFG}$ son tres arreglos lineales distintos. Además, observa que los dos primeros arreglos constan de los mismos $5$ estudiantes, lo que los hace distintos es el orden en el que están acomodados sus elementos.

Ahora, para responder a la pregunta que hicimos, vamos a valernos del principio del producto. Tenemos que considerar las $5$ posiciones (porque estamos tomando $5$ de los $10$ estudiantes que tiene el grupo) y debemos de considerar además cuántos estudiantes hay disponibles para ocupar cada posición.

\[ \underset{\substack{ \phantom{x} \\ \text{1a} \\ \text{Posicion}}}{10} \cdot \underset{\substack{ \phantom{x} \\ \text{2a} \\ \text{Posicion}}}{9} \cdot \underset{\substack{ \phantom{x} \\ \text{3a} \\ \text{Posicion}}}{8} \cdot \underset{\substack{ \phantom{x} \\ \text{4a} \\ \text{Posicion}}}{7} \cdot \underset{\substack{ \phantom{x} \\ \text{5a} \\ \text{Posicion}}}{6} \]

En la 1ᵃ posición puede ir cualquiera de los $10$ estudiantes. No es posible duplicar a los estudiantes, por lo que las repeticiones no son posibles aquí. Por ello, podemos seleccionar únicamente a alguno de los $9$ estudiantes restantes para ocupar la 2ᵃ posición. Similarmente, ahora nos quedan $8$ estudiantes para ocupar la 3ᵃ posición. Continuamos así hasta llegar a que sólo $6$ estudiantes pueden ocupar la 5ᵃ posición. Así, tenemos un total de $30{,}240$ arreglos posibles de $5$ estudiantes tomados del grupo de $10$.

Permutaciones de objetos distintos

Seguramente ya notaste que en este tipo de problemas surgen productos de enteros consecutivos (observa el ejemplo que acabamos de ver, y el ejemplo de las placas de la entrada anterior). En Álgebra Superior I puede que hayas visto el concepto de factorial. Este concepto permite una escritura más sencilla de las operaciones que aparecen en los problemas de conteo. Por ello, lo incluimos como recordatorio:

Recordatorio. Sea $n \in \mathbb{N}$. Se define el número $n$ factorial (denotado por $n!$) como sigue:

\begin{align*} 0! &= 1, \\ n! &= (n)(n − 1)(n − 2) \cdots (3)(2)(1), & \text{para $n \geq 1$}. \end{align*}

Así, se puede observar que

\begin{align*} 1! &= 1, \\ 2! &= 2 \cdot 1 = 2, \\ 3! &= 3 \cdot 2 \cdot 1 = 6, \\ 4! &= 4 \cdot 3 \cdot 2 \cdot 1 = 24, \\ 5! &= 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120. \\ \end{align*}

Además, para cualquier $n \in \mathbb{N}$ se cumple que $(n + 1)! = (n+1)(n!)$.

Utilizando la notación del factorial podemos simplificar el resultado obtenido en el último ejemplo.

\begin{align*} 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot \frac{5 \cdot 4 \cdot 3 \cdot 2\cdot 1}{5 \cdot 4 \cdot 3 \cdot 2\cdot 1} = \frac{10!}{5!}. \end{align*}

Esto es, al dividir $10!$ entre $5!$ se cancelan los últimos términos de $10!$. Efectivamente, la expresión resultante coincide con lo que obtuvimos en el ejemplo.

Definición 1.18. Dada una colección de $n$ objetos distintos, cualquer arreglo lineal formado con estos objetos es llamado una permutación de la colección.

Por ejemplo, si tenemos las letras $\mathrm{a}$, $\mathrm{b}$ y $\mathrm{c}$, hay $6$ maneras de acomodar (o permutar) estas letras: $\mathrm{abc}$, $\mathrm{acb}$, $\mathrm{bac}$, $\mathrm{bca}$, $\mathrm{cab}$ y $\mathrm{cba}$. Por otro lado, si nos interesa tomar arreglos de $2$ letras, entonces hay $6$ permutaciones de tamaño $2$ de la colección: $\mathrm{ab}$, $\mathrm{ac}$, $\mathrm{ba}$, $\mathrm{bc}$, $\mathrm{ca}$ y $\mathrm{cb}$.

Principio de las permutaciones. Sean $n, r \in \mathbb{N}$ tales que $1 \leq r \leq n$. Si tenemos $n$ objetos distintos, entonces por la regla del producto, el número de permutaciones de tamaño $r$ de los $n$ objetos es

\begin{align*} P(n,r) &= \underset{\substack{ \phantom{x} \\ \text{1a} \\ \text{Posicion}}}{(n)} \cdot \underset{\substack{ \phantom{x} \\ \text{2a} \\ \text{Posicion}}}{(n − 1)} \cdot \underset{\substack{ \phantom{x} \\ \text{3a} \\ \text{Posicion}}}{(n − 2)} \cdots \underset{\substack{ \phantom{x} \\ \text{$r$-esima} \\ \text{Posicion}}}{(n − r + 1)} \\ &= (n)(n−1)(n−2) \cdots (n−r+1) \cdot \frac{(n−r)(n−r−1) \cdots (3)(2)(1)}{(n−r)(n−r−1) \cdots (3)(2)(1)} \\ &= \frac{n!}{(n−r)!}. \end{align*}

Como mencionamos previamente, aplicamos el principio del producto para determinar el número de permutaciones que pueden hacerse a partir de una colección dada.

Algunas propiedades importantes que observar.

  1. Cuando $r = 0$, $P(n, 0) = 1 = \frac{n!}{(n−0)!}$, por lo que $P(n, r)$ está bien definido incluso para $r = 0$.
  2. Al permutar todos los $n$ objetos de la colección, se tiene $r = n$. Por ello, $P(n,n) = \frac{n!}{0!} = n!$ es el número de permutaciones posibles de todos los objetos de la colección.
  3. Es importante notar que el número de permutaciones de tamaño $r$ de una colección de $n$ objetos es un resultado del principio del producto cuando no permitimos repetición. En consecuencia, $P(n,r)$ es el número de arreglos lineales de tamaño $r$ en los que no se permiten repeticiones. Sin embargo, cuando sí permitimos las repeticiones, por el principio del producto hay $n^{r}$ arreglos lineales posibles.

Ejemplo. El número de permutaciones de las letras en la palabra $\mathrm{CARMESI}$ es $7!$, pues todas las letras son distintas entre sí. Si queremos formar permutaciones de tamaño $4$, entonces el número de permutaciones de tamaño $4$ es $P(7,4) = \frac{7!}{(7 − 4)!} = \frac{7!}{3!} = 840$. Por otro lado, si permitimos repeticiones de letras, entonces el número de cadenas de $11$ letras que podemos formar es $7^{11} = 1{,}977{,}326{,}743$.

Permutaciones con objetos repetidos

Ejemplo. ¿Qué pasa cuando nuestra colección tiene objetos repetidos o indistinguibles? Por ejemplo, ¿cuál es el número de permutaciones de las $4$ letras en la palabra $\mathrm{PALA}$? En este caso, la letra $\mathrm{A}$ se repite. Veamos cómo se ven todas las permutaciones de estas letras.

Tabla de Arreglos
$\mathrm{A \, A \, L \, P}$$\mathrm{A_{1} \, A_{2} \, L \, P}$$\mathrm{A_{2} \, A_{1} \, L \, P}$
$\mathrm{A \, A \, P \, L}$$\mathrm{A_{1} \, A_{2} \, P \, L}$$\mathrm{A_{2} \, A_{1} \, P \, L}$
$\mathrm{A \, L \, A \, P}$$\mathrm{A_{1} \, L \, A_{2} \, P}$$\mathrm{A_{2} \, L \, A_{1} \, P}$
$\mathrm{A L \, P \, A}$$\mathrm{A_{1} \, L \, P \, A_{2}}$$\mathrm{A_{2} \, L \, P \, A_{1}}$
$\mathrm{A \, P \, A \, L}$$\mathrm{A_{1} \, P \, A_{2} \, L}$$\mathrm{A_{2} \, P \, A_{1} \, L}$
$\mathrm{A \, P \, L \, A}$$\mathrm{A_{1} \, P \, L \, A_{2}}$$\mathrm{A_{2} \, P \, L \, A_{1}}$
$\mathrm{L \, A \, A \, P}$$\mathrm{L \, A_{1} \, A_{2} \, P}$$\mathrm{L \, A_{2} \, A_{1} \, P}$
$\mathrm{L \, A \, P \, A}$$\mathrm{L \, A_{1} \, P \, A_{2}}$$\mathrm{L \, A_{2} \, P \, A_{1}}$
$\mathrm{L \, P \, A \, A}$$\mathrm{L \, P \, A_{1} \, A_{2}}$$\mathrm{L \, P \, A_{2} \, A_{1}}$
$\mathrm{P \, A \, A \, L}$$\mathrm{P \, A_{1} \, A _{2}\, L}$$\mathrm{P \, A_{2} \, A _{1}\, L}$
$\mathrm{P \, A \, L \, A}$$\mathrm{P \, A_{1} \, L \, A_{2}}$$\mathrm{P \, A_{2} \, L \, A_{1}}$
$\mathrm{P \, L \, A \, A}$$\mathrm{P \, L \, A_{1} \, A_{2}}$$\mathrm{P \, L \, A_{2} \, A_{1}}$
(a)(b)

En la tabla de la izquierda (a) pusimos todos los arreglos distintos que se pueden formar con las letras que tenemos. Por otro lado, si distinguimos a las dos letras $\mathrm{A}$ como $\mathrm{A_{1}}$ y $\mathrm{A_{2}}$, nuestra colección se vuelve una colección de objetos distintos. Así, en la tabla de la derecha (b) pusimos todos los arreglos con las letras de la palabra $\mathrm{PA_{1}LA_{2}}$. En este caso sí sabemos calcular el número de permutaciones posibles, es $P(4,4) = 4! = 24$. La tabla revela que para cada arreglo en el que las $\mathrm{A}$’s son indistinguibles le corresponden dos permutaciones con $\mathrm{A}$’s distintas. En consecuencia,

\begin{align*} 2 \cdot (\text{Arreglos distintos con las letras $\mathrm{P}$, $\mathrm{A}$, $\mathrm{L}$, $\mathrm{A}$}) = (\text{Permutaciones de los simbolos $\mathrm{P}$, $\mathrm{A_{1}}$, $\mathrm{L}$, $\mathrm{A_{2}}$}), \end{align*}

por lo que la respuesta a nuestra pregunta original de encontrar todas las permutaciones de las $4$ letras en la palabra $\mathrm{PALA}$ es $\frac{4!}{2} = 12$.

Ejemplo. Usando la misma idea que desarrollamos en el ejemplo anterior, considera ahora las permutaciones de las $9$ letras de la palabra $\mathrm{COCODRILO}$.

Primero, observa que hay $3! = 6$ maneras de acomodar a las $\mathrm{O}$’s distinguidas por cada arreglo en el que las $\mathrm{O}$’s no están distinguidas. Por ejemplo, observa la siguiente tabla:

Tabla de arreglos
$\mathrm{C \, O \, C \, O \, D \, R \, I \, L \, O}$$\mathrm{C \, O_{1} \, C \, O_{2} \, D \, R \, I \, L \, O_{3}}$
$\mathrm{C \, O_{1} \, C \, O_{3} \, D \, R \, I \, L \, O_{2}}$
$\mathrm{C \, O_{2} \, C \, O_{1} \, D \, R \, I \, L \, O_{3}}$
$\mathrm{C \, O_{2} \, C \, O_{3} \, D \, R \, I \, L \, O_{1}}$
$\mathrm{C \, O_{3} \, C \, O_{1} \, D \, R \, I \, L \, O_{2}}$
$\mathrm{C \, O_{3} \, C \, O_{2} \, D \, R \, I \, L \, O_{1}}$
(a) Arreglo sin distinguir las $\mathrm{O}$’s.(b) Arreglos distinguendo a las tres letras $\mathrm{O}$.

Por cada permutación de las letras en la palabra $\mathrm{COCODRILO}$ sin distinguir a las $\mathrm{O}$’s, hay $3$ espacios ocupados por letras $\mathrm{O}$. Por ello, al distinguir a cada una, estamos permutando esas $3$ $\mathrm{O}$’s, que pueden acomodarse de $P(3,3) = 3! = 6$ maneras. Por otro lado, lo mismo pasa con las $\mathrm{C}$’s. En este caso, hay $2!$ maneras de acomodar las $\mathrm{C}$’s distinguidas por cada arreglo sin distinguir las $\mathrm{C}$’s. Por lo tanto, se tiene que

\begin{align*} (3!)(2!)(\text{Arreglos distintos con las letras en $\mathrm{COCODRILO}$}) = (\text{Permutaciones de los simbolos $\mathrm{C}_{2}$, $\mathrm{O_{1}}$, $\mathrm{C}_{2}$, $\mathrm{O_{2}}$, $\mathrm{D}$, $\mathrm{R}$, $\mathrm{I}$, $\mathrm{L}$, $\mathrm{O_{3}}$}), \end{align*}

así que el número de arreglos distintos de las $9$ letras en $\mathrm{COCODRILO}$ es $\frac{9!}{(3!)(2!)} = 30{,}240$.

Podemos enunciar un principio general para arreglos con objetos que se repiten siguiendo la idea desarrollada en los últimos ejemplos.

Permutaciones con objetos repetidos. Si tenemos una colección de $n$ objetos y dentro de esta colección tenemos $n_{1}$ objetos indistinguibles de un $1$er tipo, $n_{2}$ objetos indistinguibles de un $2$do tipo, …, y $n_{r}$ objetos indistinguibles de un $r$-ésimo tipo, de tal manera que

\[ n_{1} + n_{2} + \cdots + n_{r} = n, \]

entonces la cantidad de permutaciones de los $n$ objetos dados es

\[\frac{n!}{(n_{1}!)(n_{2}!) \cdots (n_{r}!)}. \]

Este valor es conocido como el coeficiente multinomial de $n_{1}$, $n_{2}$, …, $n_{r}$.

Ejemplo. La ciudad de $\mathrm{CONSTANTINOPLA}$ fue la ciudad capital del imperio bizantino entre los años 395 y 1204. Podemos aplicar el último principio de conteo que desarrollamos para encontrar la cantidad de permutaciones de las letras en la palabra $\mathrm{CONSTANTINOPLA}$.

Para ello, primero hay que encontrar cuántas letras distintas tiene. Observa que en total tiene $9$ letras distintas. En consecuencia, podemos pensar de cada letra distinta como un tipo de objeto. Así, tenemos $9$ tipos de objetos en la colección, y hay que contar cuántos objetos de cada tipo hay. Esto lo podemos ver en la siguiente tabla.

TipoLetraNúmero de letras de ese tipo
$1$$\mathrm{A}$$n_{1} = 2$
$2$$\mathrm{C}$$n_{2} = 1$
$3$$\mathrm{I}$$n_{3} = 1$
$4$$\mathrm{L}$$n_{4} = 1$
$5$$\mathrm{N}$$n_{5} = 3$
$6$$\mathrm{O}$$n_{6} = 2$
$7$$\mathrm{P}$$n_{7} = 1$
$8$$\mathrm{S}$$n_{8} = 1$
$9$$\mathrm{T}$$n_{9} = 2$

Además, el número de letras en $\mathrm{CONSTANTINOPLA}$ es $14$, precisamente el resultado de sumar todos los $n_{i}$. Así, obtenemos que la cantidad de premutaciones posibles de las letras en $\mathrm{CONSTANTINOPLA}$ es

\[ \frac{14!}{(2!)(1!)(1!)(1!)(3!)(2!)(1!)(1!)(2!)} = \frac{14!}{(2!)(3!)(2!)(2!)} = 1{,}816{,}214{,}400. \]

Otra pregunta que podemos resolver es, ¿cuántas permutaciones tienen a las $3$ $\mathrm{N}$’s juntas? Para verlo, podemos pensar en que la cadena de letras $\mathrm{NNN}$ es un solo símbolo, y partir de la colección de símbolos $\mathrm{A}$, $\mathrm{A}$, $\mathrm{C}$, $\mathrm{I}$, $\mathrm{L}$, $\mathrm{NNN}$ (como un solo símbolo), $\mathrm{O}$, $\mathrm{O}$, $\mathrm{P}$, $\mathrm{S}$, $\mathrm{T}$, $\mathrm{T}$, y hacer lo mismo. Así, el número de permutaciones que tiene a las $3$ $\mathrm{N}$’s juntas es

\[ \frac{12!}{(2!)(1!)(1!)(1!)(1!)(2!)(1!)(1!)(2!)} = \frac{12!}{(2!)(2!)(2!)} = 59{,}875{,}200. \]

Tarea moral

Los siguientes ejercicios son opcionales. Es decir, no formarán parte de tu calificación. Sin embargo, te recomiendo resolverlos para que desarrolles tu dominio de los conceptos abordados en esta entrada.

  1. ¿Cuántas permutaciones de los dígitos $0$, $1$, $2$, …, $9$ hay cuyo primer dígito es $3$ o cuyo último dígito es $7$?
  2. Encuentra el número de permutaciones de la palabra $\mathrm{MISSISSIPPI}$.
  3. ¿Cuántas cadenas de $13$ símbolos pueden hacerse con $6$ estrellas $*$ y $7$ barras $|$? Por ejemplo:\[ |*|*|***|*|||, \qquad ******|||||||, \qquad |*|*|*|*|*|*|. \]

Más adelante…

En la siguiente entrada continuaremos con nuestro estudio de los principios de conteo. El siguiente concepto será el de combinación, que se deriva del concepto de permutación, siendo la combinación un concepto un poco más especializado.

Por otro lado, el concepto de permutación con objetos repetidos te será de utilidad en el curso de Probabilidad II para algo que se conoce como la distribución multinomial. Cuando veamos lo que son las variables aleatorias y las funciones de distribución te quedará claro a qué nos referimos por «distribución multinomial».

Entradas relacionadas