Resumen de Análisis Combinatorio

## Introducción La combinatoria estudia de qué maneras se pueden seleccionar, ordenar o agrupar objetos cuando intervienen el orden, la repetición y las restricciones. Es una herramienta fundamental en probabilidad, informática y resolución de problemas cotidianos. > Definición: La combinatoria es la rama de las matemáticas que cuenta las posibles configuraciones de un conjunto de elementos bajo distintas reglas (ordenación, repetición, agrupamiento). ## 1. Conceptos básicos y notación ### Factorial > Definición: Para un entero no negativo $n$, el factorial $n!$ se define como el producto de los enteros desde $1$ hasta $n$, y $0! = 1$. Ejemplos: - $5! = 5\cdot4\cdot3\cdot2\cdot1 = 120$ - $11! = 1\cdot2\cdot\dots\cdot11 = 39916800$ ### Permutaciones - **Permutaciones simples (sin repetición):** ordenar todos los elementos de un conjunto de tamaño $m$ produce $m!$ arreglos. > Definición: Una permutación de $m$ elementos es un arreglo donde aparecen los $m$ elementos en algún orden. - **Permutaciones de $m$ elementos tomados de $n$ (arreglos simples):** cuando $n\le m$ y no hay repeticiones, el número de arreglos es: $$A(m,n) = m\cdot(m-1)\cdot(m-2)\cdots(m-n+1)$$ También puede expresarse con factoriales: $$A(m,n)=\frac{m!}{(m-n)!}$$ Ejemplo práctico: Con los dígitos $1,2,3,4,5$ cuántos números de $3$ cifras distintas se pueden formar: $$A(5,3)=5\cdot4\cdot3=60$$ ### Permutaciones circulares > Definición: Una permutación circular de $n$ elementos cuenta ordenamientos en un círculo donde las rotaciones se consideran iguales. Fórmula: $$P_{c}(n)=\frac{n!}{n}=(n-1)!$$ Ejemplo: Tres personas alrededor de una mesa: $P_{c}(3)=(3-1)!=2$. ### Permutaciones con repetición > Definición: Cuando entre $m$ elementos hay clases repetidas (por ejemplo letras iguales), el número de permutaciones distintas es: $$\frac{m!}{a_1!\,a_2!\,\dots\,a_k!}$$ Ejemplo: Palabras con las letras de BANANA. Aquí $m=6$ letras, con frecuencias $a_{\mathrm{B}}=1$, $a_{\mathrm{A}}=3$, $a_{\mathrm{N}}=2$, luego $$\frac{6!}{1!\,3!\,2!}=60$$ ## 2. Arreglos y combinaciones ### Arreglos simples (orden importa) > Definición: Arreglos simples de $m$ elementos tomados de a $n$ son grupos ordenados de tamaño $n$ sin repetición. Fórmula: $A(m,n)=\dfrac{m!}{(m-n)!}$. Ejemplo: Números de $4$ cifras distintas con dígitos $1$ a $5$: $$A(5,4)=\frac{5!}{(5-4)!}=\frac{120}{1}=120$$ ### Combinaciones simples (orden no importa) > Definición: Combinaciones simples de $m$ elementos tomados de a $n$ son grupos no ordenados de tamaño $n$ sin repetición. Fórmula (número combinatorio): $$C(m,n)=\binom{m}{n}=\frac{m!}{n!\,(m-n)!}$$ Ejemplo: Elegir $3$ alumnos entre $5$ para becas iguales: $$C(5,3)=\frac{5!}{3!\,2!}=10$$ ### Combinaciones con repetición > Definición: Selecciones de $n$ elementos donde cada tipo puede repetirse y el orden no importa. Fórmula: $$C_{rep}(m,n)=\binom{m+n-1}{n}=\frac{(m+n-1)!}{n!\,(m-1)!}$$ Ejemplo: Elegir $10$ caramelos entre $3$ sabores con cantidad ilimitada (o suficiente): $$C_{rep}(3,10)=\binom{3+10-1}{10}=\binom{12}{10}=66$$ ## 3. Relación entre arreglos, permutaciones y combinaciones Tabla comparativa de conceptos: | Concepto | Orden importa | Repetición permitida | Fórmula | Ejemplo corto | |---|---:|---:|---|---| | Permutación simple | Sí | No | $m!$ | Ordenar $m$ objetos | | Arreglo $A(m,n)$ | Sí | No | $\dfrac{m!}{(m-n)!}$ | Números de $n$ cifras distintas | | Combinación $C(m,n)$ | No | No | $\dfrac{m!}{n!\,(m-n)!}$ | Elegir $n$ personas | | Permutación con rep. | Sí | Sí (clases) | $\dfrac{m!}{\prod a_i!}$ | Palabras con letras repetidas | | Combinación con rep. | No | Sí | $\binom{m+n-1}{n}$ | Selección de dulces | ## 4. Fórmulas útiles y propiedades - Factorial: $n!$ y $0!=1$. - Relación arreglos-combinaciones: $A(m,n)=C(m,n)\,n!$. - Complemento en combinatorios: $\binom{m}{n}=\binom{m}{m-n}$. - Fórmula de Stiefel (suma consecutiva): $\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}$. Fun fact: El triángulo de Pasca