1.3: Combinaciones y permutaciones

Template:MathJaxLevin

¡Investiga!

Tienes un montón de chips que vienen en cinco colores diferentes: rojo, azul, verde, morado y amarillo.

1. ¿Cuántas pilas diferentes de dos fichas puedes hacer si la ficha inferior debe ser roja o azul? Explica tu respuesta usando los principios aditivos y multiplicativos.
2. ¿Cuántas pilas diferentes de tres fichas puedes hacer si la ficha inferior debe ser roja o azul y la ficha superior debe ser verde, morada o amarilla? ¿Cómo se relaciona este problema con el anterior?
3. ¿Cuántas pilas diferentes de tres fichas hay en las que no se repite ningún color? ¿Qué pasa con las pilas de cuatro fichas?
4. Supongamos que querías tomar tres chips de diferentes colores y meterlos en tu bolsillo. ¿Cuántas opciones diferentes tienes? ¿Y si quisieras cuatro chips de diferentes colores? ¿Cómo se relacionan estos problemas con el anterior?

Una permutación es un (posible) reordenamiento de objetos. Por ejemplo, hay 6 permutaciones de las letras a, b, c:

\ begin {ecuación*} abc, ~~ acb, ~~ bac, ~~bca, ~~ cab, ~~ cba. \ end {ecuación*}

Sabemos que los tenemos todos enumerados anteriormente —hay 3 opciones para qué letra ponemos primero, luego 2 opciones para qué letra viene a continuación, lo que deja solo 1 opción para la última letra. El principio multiplicativo dice que multiplicamos$3\cdot 2 \cdot 1\text{.}$

Ejemplo$\PageIndex{1}$

¿Cuántas permutaciones hay de las letras a, b, c, d, e, f?

Contestar

NO queremos intentar enumerar todos estos hacia fuera. No obstante, si lo hiciéramos, tendríamos que elegir una carta para anotar primero. Hay 6 opciones para esa carta. Para cada elección de primera letra, hay 5 opciones para la segunda letra (no podemos repetir la primera letra; estamos reordenando letras y solo tenemos una de cada una), y para cada una de ellas, hay 4 opciones para la tercera, 3 opciones para la cuarta, 2 opciones para la quinta y finalmente solo 1 opción para la última letra. Así que hay$6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$ permutations of the 6 letters.

Una pieza de notación es útil aquí:$n!\text{,}$ leer “$n$factorial”, es el producto de todos los enteros positivos menores o iguales a$n$ (por razones de conveniencia, también definimos 0! ser 1). Entonces el número de permutación de 6 letras, como se ve en el ejemplo anterior es$6! = 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\text{.}$ Esto generaliza:

Permutaciones de$n$ elements

Hay$n! = n\cdot (n-1)\cdot (n-2)\cdot \cdots \cdot 2\cdot 1$ permutaciones de elementos$n$ (distintos).

Funciones biyectivas de conteo

¿Cuántas funciones$f:\{1,2,\ldots,8\} \to \{1,2,\ldots, 8\}$ son biyectivas?

Solución

Recuerda lo que significa que una función sea biyectiva: cada elemento en el codominio debe ser la imagen de exactamente un elemento del dominio. Usando la notación de dos líneas, podríamos escribir una de estas bijecciones como

\ begin {ecuación*} f =\ twoline {1\ amp 2\ amp 3\ amp 4\ amp 5\ amp 6\ amp 7\ amp 8} {3\ amp 1\ amp 5\ amp 8\ amp 7\ amp 6\ amp 2\ amp 4}\ end {ecuación*}

Lo que realmente estamos haciendo es simplemente reorganizar los elementos del codominio, por lo que estamos creando una permutación de 8 elementos. De hecho, “permutación” es otro término utilizado para describir funciones biyectivas desde un conjunto finito a sí mismo.

Si crees esto, entonces ves que la respuesta debe ser$8! = 8 \cdot 7 \cdot\cdots\cdot 1 = 40320\text{.}$ You can see this directly as well: for each element of the domain, we must pick a distinct element of the codomain to map to. There are 8 choices for where to send 1, then 7 choices for where to send 2, and so on. We multiply using the multiplicative principle.

A veces no queremos permutar todas las letras/números/elementos que se nos dan.

Ejemplo$\PageIndex{3}$

¿Cuántas “palabras” de 4 letras puedes hacer de las letras de la a a a la f, sin letras repetidas?

Solución

Esto es igual que el problema de permutar 4 letras, solo que ahora tenemos más opciones para cada letra. Para la primera letra, hay 6 opciones. Para cada una de esas, hay 5 opciones para la segunda letra. Luego hay 4 opciones para la tercera letra, y 3 opciones para la última letra. El número total de palabras es\(6\cdot 5\cdot 4 \cdot 3 = 360\text{.}\) This is not \(6!\) because we never multiplied by 2 and 1. We could start with \(6!\) and then cancel the 2 and 1, and thus write \(\frac{6!}{2!}\text{.}\)

En general, podemos preguntar cuántas permutaciones existen de$k$ objetos eligiendo esos objetos de una colección más grande de$n$ objetos. (En el ejemplo anterior,$k = 4\text{,}$ y$n = 6\text{.}$) Escribimos este número$P(n,k)$ y a veces lo llamamos una $k$-permutación de$n$ elementos. Del ejemplo anterior, vemos que para calcular$P(n,k)$ debemos aplicar el principio multiplicativo a$k$ los números, empezando por$n$ y contando hacia atrás. Por ejemplo

\ begin {ecuación*} P (10, 4) = 10\ cdot 9\ cdot 8\ cdot 7. \ end {ecuación*}

Observe de nuevo que$P(10,4)$ empieza pareciendo$10!\text{,}$ pero nos detenemos después de las 7. Podemos dar cuenta formalmente de esta “detención” dividiendo la parte del factorial que no queremos:

\ begin {ecuación*} P (10,4) =\ frac {10\ cdot 9\ cdot 8\ cdot 7\ cdot 6\ cdot 5\ cdot 4\ cdot 3\ cdot 2\ cdot 1} {6\ cdot 5\ cdot 4\ cdot 3\ cdot 2\ cdot 1} =\ frac {10!} {6!}. \ end {ecuación*}

Cuidado: El factorial en el denominador no es$4!$ sino más bien$(10-4)!\text{.}$

$k$-permutations of $n$ elements

$P(n,k)$es el número de$k$ -permutaciones de$n$ elementos, el número de formas de organizar$k$ objetos elegidos de$n$ distintos objetos.

\ comenzar {ecuación*} P (n, k) =\ frac {n!} {(n-k)!}. \ end {ecuación*}

Tenga en cuenta que cuando$n = k\text{,}$ tenemos$P(n,n) = \frac{n!}{(n-n)!} = n!$ (ya que$0!$ definimos que es 1). Esto tiene sentido —ya sabemos$n!$ da el número de permutaciones de todos los$n$ objetos.

Contando las funciones inyectoras

¿Cuántas funciones$f:\{1,2,3\} \to \{1,2,3,4,5,6,7,8\}$ son inyectivas?

Solución

Tenga en cuenta que no tiene sentido pedir el número de bijecciones aquí, ya que no hay ninguna (porque el codominio es mayor que el dominio, no hay surjecciones). Pero para que una función sea inyectiva, simplemente no podemos usar un elemento del codominio más de una vez.

Necesitamos escoger un elemento del codominio para que sea la imagen de 1. Hay 8 opciones. Entonces tenemos que escoger uno de los 7 elementos restantes para que sea la imagen de 2. Por último, uno de los 6 elementos restantes debe ser la imagen de 3. Entonces el número total de funciones es$8\cdot 7 \cdot 6 = P(8,3)\text{.}$

Lo que esto demuestra en general es que el número de inyecciones$f:A \to B\text{,}$ where $\card{A} = k$ and $\card{B} = n\text{,}$ is $P(n,k)\text{.}$

Aquí hay otra manera de encontrar el número de$k$ -permutaciones de$n$ elementos: primero seleccione qué$k$ elementos estarán en la permutación, luego cuente cuántas formas hay de organizarlos. Una vez que haya seleccionado los$k$ objetos, sabemos que hay$k!$ formas de organizarlos (permutarlos). Pero, ¿cómo se seleccionan$k$ los objetos del$n\text{?}$ Tienes$n$ objetos, y tienes que elegir$k$ de ellos? Eso se puede hacer de${n \choose k}$ maneras. Entonces para cada elección de esos$k$ elementos, podemos permutarlos de$k!$ maneras. Usando el principio multiplicativo, obtenemos otra fórmula para$P(n,k)\text{:}$

\ comenzar {ecuación*} P (n, k) = {n\ elige k}\ cdot k!. \ end {ecuación*}

Ahora como tenemos una fórmula cerrada para$P(n,k)$ ya, podemos sustituirla en:

\ comenzar {ecuación*}\ frac {n!} {(n-k)!} = {n\ elige k}\ cdot k!. \ end {ecuación*}

Si dividimos ambos lados por$k!$ obtenemos una fórmula cerrada para${n \choose k}\text{.}$

Fórmula cerrada para${n \choose k}$

\ comenzar {ecuación*} {n\ elige k} =\ frac {n!} {(n-k)! k!} \ end {ecuación*}

Decimos$P(n,k)$ cuentas permutaciones, y${n \choose k}$ cuentas combinaciones. Las fórmulas para cada una son muy similares, solo hay un extra$k!$ en el denominador de${n \choose k}\text{.}$ Ese extra da$k!$ cuenta del hecho de que${n \choose k}$ no distingue entre los diferentes órdenes en los que pueden aparecer$k$ los objetos. Simplemente estamos seleccionando (o eligiendo) los$k$ objetos, no ordenándolos. Quizás “combinación” sea una etiqueta engañosa. No lo queremos decir como una cerradura de combinación (donde definitivamente importaría el orden). Quizás una mejor metáfora es una combinación de sabores — sólo hay que decidir qué sabores combinar, no el orden en que combinarlos.

Para ilustrar mejor la conexión entre combinaciones y permutaciones, cerramos con un ejemplo.

Ejemplo$\PageIndex{5}$

Tú decides tener una cena. A pesar de que eres increíblemente popular y tienes 14 amigos diferentes, solo tienes suficientes sillas para invitar a 6 de ellos.

1. ¿Cuántas opciones tienes para qué 6 amigos invitar?
2. ¿Y si necesitas decidir no solo a qué amigos invitar sino también a dónde sentarlos a lo largo de tu larga mesa? ¿Cuántas opciones tienes entonces?

Solución

1. Simplemente debes elegir 6 amigos de un grupo de 14. Esto se puede hacer de${14 \choose 6}$ maneras. Podemos encontrar este número ya sea usando el triángulo de Pascal o la fórmula cerrada:$\frac{14!}{8!\cdot 6!} = 3003\text{.}$
2. Aquí debes contar todas las formas en las que puedes permutar a 6 amigos elegidos de un grupo de 14. Entonces la respuesta es$P(14, 6)\text{,}$ que se puede calcular como$\frac{14!}{8!} = 2192190\text{.}$

Observe que podemos pensar en este problema de conteo como una pregunta sobre el conteo de funciones: cuántas funciones inyectivas hay desde tu conjunto de 6 sillas hasta tu conjunto de 14 amigos (las funciones son inyectoras porque no puedes tener una sola silla ir a dos de tus amigos).

¿Cómo se relacionan estos números? Observe que$P(14,6)$ es mucho más grande que${14 \choose 6}\text{.}$ Esto tiene sentido. ${14 \choose 6}$recoge 6 amigos, pero$P(14,6)$ organiza los 6 amigos así como los elige. De hecho, podemos decir exactamente cuánto más grande$P(14,6)$ es. En ambos problemas de conteo elegimos 6 de 14 amigos. Para el primero, paramos ahí, a 3003 vías. Pero para el segundo problema de conteo, cada una de esas 3003 opciones de 6 amigos se pueden organizar de$6!$ manera exacta. Así que ahora tenemos$3003\cdot 6!$ opciones y eso es exactamente$2192190\text{.}$

Alternativamente, mira el primer problema de otra manera. Queremos seleccionar 6 de 14 amigos, pero no nos importa el orden en que se seleccionen. Para seleccionar 6 de 14 amigos, podríamos probar esto:

\ begin {ecuación*} 14\ cdot 13\ cdot 12\ cdot 11\ cdot 10\ cdot 9. \ end {ecuación*}

Esta es una suposición razonable, ya que tenemos 14 opciones para el primer invitado, luego 13 para el segundo, y así sucesivamente. Pero la conjetura es incorrecta (de hecho, ese producto es exactamente$2192190 = P(14,6)$). Distingue entre los diferentes órdenes en los que podríamos invitar a los invitados. Para corregir esto, podríamos dividir por el número de arreglos diferentes de los 6 invitados (para que todos estos contaran como un solo resultado). Hay precisamente$6!$ formas de organizar 6 invitados, por lo que la respuesta correcta a la primera pregunta es

\ begin {ecuación*}\ frac {14\ cdot 13\ cdot 12\ cdot 11\ cdot 10\ cdot 9} {6!}. \ end {ecuación*}

Tenga en cuenta que otra forma de escribir esto es

\ comenzar {ecuación*}\ frac {14!} {8! \ cdot 6!}. \ end {ecuación*}

que es lo que teníamos originalmente.