Permutaciones

Introducción a los Arreglos Ordenados

Las permutaciones son un concepto fundamental en la combinatoria que describe todos los posibles arreglos ordenados de los elementos en un conjunto dado. En las permutaciones, se utilizan todos los elementos y su disposición es importante. Cada cambio en el orden de los elementos crea una permutación diferente, lo que las distingue de las combinaciones, donde el orden no importa. Si tenemos n elementos distintos, el número de todas las posibles permutaciones de estos elementos es: P(n) = n! (n factorial), donde n! = n * (n – 1) * (n – 2) * … * 2 * 1

Ejemplo 1: Permutaciones Básicas

¿Cuántos arreglos diferentes de las letras A, B y C existen? n = 3 → P(3) = 3! = 6 Las permutaciones son: ABC, ACB, BAC, BCA, CAB, CBA.

Permutaciones con Repetición

Si un conjunto contiene elementos que se repiten, entonces intercambiar elementos idénticos no crea una nueva permutación. En este caso, el número de permutaciones se reduce dividiendo por los factoriales del número de repeticiones. Si tenemos n elementos, de los cuales:

• r₁ son del primer tipo idéntico,

• r₂ son del segundo tipo idéntico,

• …,

• rₖ son del k-ésimo tipo idéntico, entonces la fórmula es: P(n; r₁, r₂, …, rₖ) = n! / (r₁! * r₂! * … * rₖ!)

Ejemplo 2: Permutaciones con Elementos Repetidos

¿Cuántas permutaciones diferentes tiene la palabra MAMA? Letras: M aparece 2 veces, A aparece 2 veces → n = 4, r₁ = 2, r₂ = 2 P = 4! / (2! * 2!) = 24 / (2 * 2) = 6 Las permutaciones son: MAMA, MAAM, AMMA, AAMM, AMAM, MMAA.

Permutaciones Circulares

Cuando ordenamos elementos en un círculo, estamos tratando con permutaciones circulares. En un círculo, las rotaciones del mismo arreglo no se consideran nuevas permutaciones. Para n elementos distintos en un círculo, la fórmula es: P_circular(n) = (n – 1)!

• Ejemplo: Ordenar a 5 personas alrededor de una mesa → (5 – 1)! = 4! = 24 posibilidades.

Conexión con Variaciones y Combinaciones

• Permutaciones: Usa todos los elementos, el orden es importante.

• Variaciones: Usa un subconjunto de elementos, el orden es importante.

• Combinaciones: Usa un subconjunto de elementos, el orden no es importante.

Aplicaciones de las Permutaciones

Las permutaciones se utilizan para:

• Ordenar personas, objetos o caracteres.

• Codificación y creación de contraseñas.

• Reorganizar elementos sin repetición.

• Resolver problemas en teoría de juegos y optimización.

Conclusión

Las permutaciones representan todas las formas posibles de ordenar elementos donde la secuencia es crucial. El número de permutaciones crece rápidamente con el número de elementos. Comprender las diferentes formas de permutaciones es esencial para resolver eficazmente los problemas combinatorios.