Permutaciones y Combinaciones
Las permutaciones cuentan arreglos ordenados de objetos y las combinaciones cuentan selecciones no ordenadas; juntas forman el núcleo elemental de la enumeración.
Definition
Una permutación de un conjunto es un arreglo ordenado de sus elementos (o una biyección del conjunto a sí mismo); una combinación es una selección no ordenada de un número fijo de elementos de un conjunto.
Scope
Este tema desarrolla el conteo de arreglos (con y sin repetición), selecciones y sus refinamientos, incluyendo desórdenes, permutaciones circulares y permutaciones con posiciones restringidas. Introduce estadísticas de permutación como descensos, inversiones y estructura de ciclos, que conectan el conteo elemental con la teoría moderna más rica del grupo simétrico.
Core questions
- ¿De cuántas maneras se pueden ordenar n objetos distintos, y de cuántas maneras se pueden ordenar r de ellos?
- ¿Cómo cambian la repetición y la indistinguibilidad el conteo de arreglos?
- ¿Qué son los desórdenes y con qué frecuencia una permutación aleatoria no fija ningún elemento?
- ¿Qué estadísticas sobre permutaciones están equidistribuidas?
Key concepts
- Factorial y factorial descendente
- Arreglos con y sin repetición
- Desórdenes
- Permutaciones circulares
- Inversiones y descensos
- Números de Stirling
Key theories
- Descomposición en ciclos de permutaciones
- Cada permutación se factoriza de forma única en ciclos disjuntos; el conteo de permutaciones por su tipo de ciclo se rige por los números de Stirling de primera especie y subyace a la estructura del grupo simétrico.
- Enumeración de desórdenes
- El número de permutaciones sin punto fijo, derivado mediante inclusión-exclusión, se aproxima a n!/e, dando el resultado clásico de que aproximadamente el 37% de las permutaciones son desórdenes.
Clinical relevance
Los conteos de permutaciones y combinaciones aparecen en probabilidad (resultados igualmente probables), algoritmos de clasificación y mezcla, diseño experimental y espacios de claves criptográficas, donde el tamaño de un espacio de arreglo determina la dificultad y la seguridad.
History
La combinatoria de permutaciones fue sistematizada por el trabajo de MacMahon a principios del siglo XX sobre el análisis combinatorio y posteriormente profundizada a través de la teoría moderna de las estadísticas de permutación.
Key figures
- Percy MacMahon
- Richard P. Stanley
Related topics
Seminal works
- stanley2011
Frequently asked questions
- ¿Cuántas permutaciones tiene un conjunto de n elementos?
- Tiene n! permutaciones, el producto de todos los enteros positivos hasta n, ya que cada una de las n posiciones se llena con un elemento distinto restante.
- ¿Qué es un desorden?
- Un desorden es una permutación en la que ningún elemento permanece en su posición original, como una reorganización donde ninguna carta vuelve a su propio sobre.