Permutaciones

Teoría

Una permutación es un acomodo específico de un conjunto de objetos en un orden definido. A diferencia de las combinaciones, donde la selección de los elementos importa pero su secuencia no, las permutaciones se enfocan estrictamente en el orden lineal de los elementos. Por ejemplo, en una carrera con 8 corredores, el conjunto de los medallistas (los mejores 3) es una combinación, pero la asignación específica de Oro, Plata y Bronce es una permutación. Este concepto es fundamental en la combinatoria porque cuantifica de cuántas formas puedes realizar distintas operaciones en secuencia.

El cálculo de las permutaciones se basa mucho en el Principio de Multiplicación (o Principio Fundamental del Conteo). La mejor forma de entender la intuición es con el "método de las casillas": si tienes $n$ objetos distintos para poner en $n$ casillas distintas, tienes $n$ opciones para la primera casilla. Una vez que llenas esa casilla, tienes $n-1$ opciones para la segunda, $n-2$ para la tercera, y así sucesivamente, hasta que solo te queda 1 opción para la última casilla. El número total de acomodos es el producto de estas opciones.

Las permutaciones aparecen seguido en las matemáticas de competencia, desde problemas simples de anagramas en el AMC 8 hasta problemas complejos de probabilidad y teoría de grupos en el AMC 12 y el AIME. Dominar las permutaciones incluye entender no solo los acomodos lineales de objetos distintos, sino también variaciones avanzadas como permutaciones parciales (acomodar un subconjunto de objetos), permutaciones de multiconjuntos (objetos que no puedes distinguir) y permutaciones circulares (donde los acomodos que son iguales al rotarlos cuentan como el mismo).

Fórmulas Clave

1. Notación Factorial El producto de todos los enteros positivos hasta $n$ lo escribimos como $n!$: $$n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$$ Por definición, $0! = 1$.

2. Permutaciones de $n$ Objetos Distintos El número de formas de acomodar $n$ objetos distintos en una fila es: $$P(n, n) = n!$$

3. Permutaciones Parciales ($k$-permutaciones de $n$) El número de formas de acomodar $k$ objetos elegidos de un conjunto de $n$ objetos distintos (donde $0 \le k \le n$) lo denotamos como $P(n,k)$ o $_nP_k$: $$P(n, k) = \frac{n!}{(n-k)!}$$

4. Permutaciones con Repetición (Multiconjuntos) Si hay $n$ objetos, donde $n_1$ son iguales de un tipo, $n_2$ son iguales de otro tipo, ..., y $n_k$ son iguales de un $k$-ésimo tipo, de tal forma que $n_1 + n_2 + \dots + n_k = n$, el número de formas distintas de acomodarlos es: $$ \frac{n!}{n_1! n_2! \dots n_k!} $$

5. Permutaciones Circulares El número de formas de acomodar $n$ objetos distintos alrededor de un círculo, donde las rotaciones cuentan como el mismo acomodo, es: $$ Q_n = \frac{n!}{n} = (n-1)! $$ Nota: Si puedes voltear el acomodo (como las cuentas de un collar), el número de formas es $\frac{(n-1)!}{2}$.

Demostración

Teorema: El número de permutaciones de $k$ objetos elegidos de un conjunto de $n$ objetos distintos es $P(n,k) = \frac{n!}{(n-k)!}$.

Demostración: Usa el Principio de Multiplicación (Principio Fundamental del Conteo) para armar un acomodo ordenado de longitud $k$ usando elementos de un conjunto $S$ donde $|S| = n$.

Imagina que tienes $k$ posiciones vacías para llenar: posición 1, posición 2, ..., posición $k$.

1. Primera Posición: Como hay $n$ objetos distintos en el conjunto, tienes $n$ opciones posibles para llenar la primera posición.
2. Segunda Posición: Después de llenar la primera posición, ya usaste un objeto. Quedan $n-1$ objetos. Por lo tanto, tienes $n-1$ opciones para la segunda posición.
3. Tercera Posición: Ya usaste dos objetos. Quedan $n-2$ objetos. Así que tienes $n-2$ opciones.

Sigue con este patrón. Para la $i$-ésima posición, ya usaste $i-1$ objetos, así que quedan $n - (i-1)$ opciones.

4. $k$-ésima Posición: Para cuando llegas a la última posición, ya usaste $k-1$ objetos. Por lo tanto, el número de opciones para la $k$-ésima posición es $n - (k-1) = n - k + 1$.

Por el Principio de Multiplicación, el número total de formas de llenar las $k$ posiciones es el producto del número de opciones de cada paso: $$ P(n,k) = n \times (n-1) \times (n-2) \times \dots \times (n - k + 1) $$

Para escribir esto de forma más compacta usando la notación factorial, multiplica la expresión por $\frac{(n-k)!}{(n-k)!}$ (que es igual a 1):

$$ P(n,k) = \frac{n \times (n-1) \times \dots \times (n - k + 1) \times (n-k)!}{(n-k)!} $$

Fíjate en el numerador. Es el producto de los enteros empezando desde $n$, bajando hasta $n-k+1$, y luego siguiendo con $(n-k)!$ (que se expande como $(n-k) \times (n-k-1) \times \dots \times 1$). Esto forma el producto completo desde $n$ hasta $1$.

Así que el numerador es exactamente $n!$.

$$ P(n,k) = \frac{n!}{(n-k)!} $$

$\square$