Permutación
Una permutación es un arreglo de objetos en un orden específico, donde el orden importa.
Formula
P(n, r) = \dfrac{n!}{(n-r)!}
Definition
Una permutación es una forma de organizar un grupo de cosas en un orden específico; las permutaciones cuentan cuántos arreglos ordenados diferentes son posibles. Una permutación de $n$ elementos tomados de $r$ en $r$ es una selección ordenada: $P(n,r) = n!/(n-r)!$, y el número total de permutaciones de $n$ elementos distintos es $n!$. Formalmente, para objetos con repetición (permutaciones de multiconjunto), el conteo es $n!/(n_1!n_2!\cdots n_k!)$ donde $n_i$ es el conteo del $i$-ésimo objeto distinto, el coeficiente multinomial; los grupos de permutaciones (grupos simétricos $S_n$) son fundamentales en el álgebra abstracta, siendo $S_3$ (todas las permutaciones de $3$ objetos) el grupo no abeliano más pequeño.
Example
¿De cuántas formas pueden $3$ estudiantes terminar primero, segundo, y tercero en una carrera de $5$ estudiantes? $P(5,3) = 5 \times 4 \times 3 = 60$ formas, ya que el orden importa (1ro, 2do, 3ro son lugares distintos). Un PIN de $4$ dígitos creado a partir de los dígitos $1$-$9$ sin repetición tiene $P(9,4) = 9!/5! = 3{,}024$ posibilidades. La palabra MISSISSIPPI tiene $11$ letras ($M(1)$, $I(4)$, $S(4)$, $P(2)$), así que el número de arreglos distintos es $11!/(1! \cdot 4! \cdot 4! \cdot 2!) = 34{,}650$.
Key Insight
La pregunta clave para permutaciones frente a combinaciones es si el orden importa: ABC y CBA son la misma combinación pero permutaciones diferentes. Los grupos de permutaciones conectan la combinatoria con la teoría de grupos y la física (simetrías de partículas), ya que $S_3$ tiene $6$ elementos y es el grupo no abeliano más pequeño.