Tutorial: Permutaciones y combinaciones

Versión juego adaptivo

(Se puede encontrar este tema en a Sección 6.4 del libro Matemáticas finitas o la Sección 7.4 en el libro Matemáticas finitas y cálculo aplicado)

¿Qué es un tutorial juego adaptivo? ▶

No me gusta este nuevo tutorial. ¡Llévame de vuelta a la versión antigua de este tutorial

#[Resources][Recursos]#

Calculador pop-up de factoriales, permutaciones y combinaciones

%%Note Muchos de los conceptos de este tutorial se basan en algoritmos de decisión, por lo que es posible que desee ir al %%prevsectut para revisar esos conceptos.

Permutaciones

Empecemos con un ejercicio de calentamiento basado en el %%prevsectut

Llamamos a una lista ordenada de objetos (como las que estamos ordenando en el calentamiento) una permutación de aquellos objetos.

%%Q Por lo general, si tenemos $n$ objetos, entonces ¿cuántas permutaciones son posibles de aquellos objetos?
%%A Podemos utilizar un algoritmo de decisión parecido a lo que usamos más arriba para formar una permutación:

Paso 1: Elige el primero objeto; $n$ elecciones.
Paso 2: Elige el segundo objeto; $n - 1$ elecciones.
Paso 3: Elige el tercero objeto; $n - 2$ elecciones.
...
Paso $n - 1$: Elige el penúltimo objeto; 2 elecciones.
Paso $n$: Elige el último objeto; 1 elección.

Por lo tanto, por el principio multiplicativo, hay $n \times (n - 1) \times (n - 2) \times ... \times 2 \times 1$ permutaciones posibles. Llammos a este número $n$ factorial, que escribimos como $n!$.

Permutaciones de n objetos
Una permutación de $n$ objetos es una lista ordenada de todos estos objetos. El número de permutaciones diferentes posibles de $n$ objetos es la factorial de $n$, dado por

$n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1$

cuando $n$ es un entero positivo. También defininimos

$0! = 1.$

%%Examples

1. $\ 1!$ \t ${}= 1$ \\ $2!$ \t ${}= 2 \times 1 = 2$ \\ $3!$ \t ${}= 3 \times 2 \times 1 = 6$ \\ $10!$ \t ${}= 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1$ \\ \t ${}= 3,628,800$

2. #[The number ways of ordering the digits 1, 2, 3 is $3! = 3 \times 2 \times 1 = 6.$ \t Here are the 6 orderings:][El número de ordenamientos de los dígitos 1, 2, 3 son $3! = 3 \times 2 \times 1 = 6.$ \t Aquí están los 6 ordenamientos:]#

\\ $123,132,213,231,312,321$

#[Some for you][Algunas para ti]#

%%Q ¿Qué pasa si queremos hacer una lista ordenada de solo algunos de los elementos (como en el calentamiento anterior)?
%%A Podemos utilizar el siguiente algoritmo de decisión para formar una permutación usando solo $r$ de los $n$ elementos disponibles:

Paso 1: Elige el primero objeto; $n$ elecciones.
Paso 2: Elige el segundo objeto; $n - 1$ elecciones.
Paso 3: Elige el tercero objeto; $n - 2$ elecciones.
...
Paso $r$: Elige el $r$º objeto; $n - r + 1$ elecciones.

Por lo tanto, por el principio multiplicativo, hay $n \times (n - 1) \times (n - 2) \times ... \times (n-r+1)$ permutaciones posibles usando $r$ de los $n$ objetos.

Permutaciones de r objetos tomados de entre n objetos
Una permutación de $r$ objetos tomados de entre $n$ objetos (o una permutación de $n$ elementos tomados de $r$ en $r$) es una lista ordenada de $r$ objetos escogidos de un conjunto de $n$ objetos. El número de permutaciones de $r$ objetos tomados de entre $n$ objetos se expresa por

$P(n, r) = n \times (n - 1) \times (n - 2) \times ... \times (n - r + 1)$ \t #[Product of $r$ terms starting with $n$][Producto de $r$ términos que comienzan con $n$]#

La siguiente es una formula alternativa que se usa frecuentemente para calcular la misma cantidad:

$P(n, r) = \dfrac{n!}{(n - r)!}$

%%Examples

1. $P(4, 2) = 4 \times 3 = 12$

\t #[Product of 2 terms starting with 4][Producto de 2 términos comenzando con 4]# \\

$\quad P(10, 3) = 10 \times 9 \times 8 = 720$

\t #[Product of 3 terms starting with 10][Producto de 3 términos comenzando con 10]# \\

$\quad P(12, 1) = 12$

\t #[Product of 1 term starting with 12][Producto de 1 término comenzando con 12]# \\

$\quad P(5, 5) = 5 \times 4 \times 3 \times 2 \times 1 = 5!$

\t #[Product of 5 terms starting with 5][Producto de 5 términos comenzando con 5]#

2. #[The number of possible sequences of three of the digits 1, 2, 3, ..., 9 is $P(9,3) = 9 \times 8 \times 7 = 504$

This is the number of three-digit sequences that exclude 0.

][El número de secuencias posibles de tres de los dígitos 1, 2, 3, ..., 9 es $P(9,3) = 9 \times 8 \times 7 = 504$ \t Este es el número de secuenciass de tres dígitos que excluyen 0.]#

#[Some for you][Algunas para ti]#

Combinaciones

%%Q ¿Qué pasa si el orden no es importante? Por ejemplo, si elijo un grupo de 3 de mis 5 amigos para que me acompañen al cine, el orden en que los elijo no es importante. Entonces, el número de resultados posibles no puede ser $P(5,3)$ porque ese sería el número de listas ordenadas de 3 amigos. ¿Cuál es entonces el número correcto?
%%A Para ver la respuesta correcta, piensa por qué $P(5, 3)$ es la respuesta incorrecta: los mismos tres amigos aparecerán en muchas listas diferentes; de hecho, en 3! = 6 listas (el número de maneras de organizar los 3 amigos). Por lo tanto, la razón por la que $P(5,3)$ es incorrecto es que es 6 veces demasiado grande, por lo que la respuesta correcta debería ser 1/6 de eso.

$\dfrac{P(5, 3)}{3!} = \dfrac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10.$

Combinaciones de r objetos tomados de entre n objetos
Una combinación de $r$ objetos tomados de entre $n$ objetos (o una combinación de $n$ elementos tomados de $r$ en $r$) es una es una colección no ordenada o conjunto de $r$ objetos escogidos de un conjunto de $n$ objetos. El número de combinaciones de $r$ objetos tomados de entre $n$ objetos se expresa por

$C(n, r) = \dfrac{n \times (n - 1) \times ... \times (n - r + 1)}{r \times (r - 1) \times ... \times 1} = \dfrac{P(n,r)}{r!} \quad$ \t #[Compare with the formula for $P(n, r)$ above][Compara con la fórmula para $P(n, r)$ anterior]#

La fórmula alternativa para $P(n,r)$ que vimos arriba nos da la siguiente fórmula alternativa para $C(n,r):$

$C(n, r) = \dfrac{n!}{r!(n - r)!}$

%%Examples

$\quad C(4, 2) = \dfrac{4 \times 3}{2 \times 1} = 6$

\t 2 términos tanto en el numerador como en el denominador. \\

$\quad C(10, 3) = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

\t 3 términos tanto en el numerador como en el denominador. \\

$\quad C(12, 1) = \dfrac{12}{1} = 12$

\t 1 término tanto en el numerador como en el denominador. \\

$\quad C(5, 5) = \dfrac{5 \times 4 \times 3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1} = 1!$

\t Por lo general, $C(n,n) = 1$ \\

$\quad C(7, 5) = \dfrac{7 \times 6 \times {} \color{red}{5 \times 4 \times 3}}{\color{red}{5 \times 4 \times 3} \times 2 \times 1} = \dfrac{7 \times 6}{2 \times 1}$
$\qquad = C(7,2) = 21 \qquad$

\t Por lo general, $C(n,r) = C(n,n-r)$ \\

$\quad C(10, 7) = C(10,3) = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

\t Vea comentario anterior. \\

$\quad C(10, 0) = C(10,10) = 1$

\t Por lo general, $C(n,0) = 1$

#[Some for you][Algunas para ti]#

Ahora prueba algunos de los ejercicios en a Sección 6.4 del libro Matemáticas finitas o la Sección 7.4 en el libro Matemáticas finitas y cálculo aplicado.