Lección 37 — Permutaciones y arreglos

Definiciones

Factorial

$n! = n \cdot (n-1) \cdot (n-2) \cdots 1$. Convención: $0! = 1$.

Crecimiento:

Aproximación de Stirling: $n! \approx \sqrt{2\pi n}(n/e)^n$.

Permutación simple

$P_n = n!$: formas de ordenar $n$ objetos distintos en fila.

Permutación con repetición

Para $n$ objetos con $n_1$ del tipo 1, $n_2$ del tipo 2, ..., $n_k$ del tipo $k$: $P_n^{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! \cdot n_2! \cdots n_k!}$

Anagramas de "ARARA" (3 A, 2 R): $5!/(3! \cdot 2!) = 10$.

Arreglo simple

$A_n^p = n(n-1)(n-2) \cdots (n-p+1) = \frac{n!}{(n-p)!}$

Formas de ordenar $p$ objetos seleccionados de $n$ disponibles.

Permutación circular

$n$ objetos en círculo: $(n-1)!$. Razón: la "primera posición" es arbitraria.

Diferencia entre permutación y arreglo

• Permutación: usa todos los $n$ objetos.
• Arreglo: selecciona $p \leq n$ y los ordena.

Cuando $p = n$: el arreglo coincide con la permutación.