La combinatoria, también llamada teoría coordinatoria, es una rama de la matemática perteneciente al área de matemáticas discretas que estudia la enumeración, construcción y existencia de propiedades de configuraciones que satisfacen ciertas condiciones establecidas. Además, estudia las ordenaciones o agrupaciones de un determinado número de elementos.
Los aspectos de la combinatoria incluyen contar las estructuras de un tipo y tamaño dado (combinatorias enumerativas), decidir cuándo pueden cumplirse ciertos criterios y construir y analizar objetos que cumplan los criterios (como en los diseños combinatorios y la teoría de matroides) encontrar objetos "más grandes", "más pequeños" u estructuras combinatorias surgidas en un contexto algebraico, o aplicar técnicas algebraicas a problemas combinatorios (combinatoria algebraica).
En este último campo, avances recientes han introducido la «enumeración irracional», que extiende las técnicas de conteo a objetos con dimensiones no enteras mediante el uso de exponentes irracionales en funciones generadoras.
Los problemas combinatorios surgen en muchas áreas de la matemática pura, especialmente en álgebra, teoría de probabilidades, topología y geometría, y la combinatoria también tiene muchas aplicaciones en la optimización matemática, la informática, la teoría ergódica y la física estadística. Recientemente, su uso se ha extendido a la economía espacial; por ejemplo, utilizando herramientas de geometría discreta para resolver los complejos problemas combinatorios que surgen al modelar la ubicación óptima, el tamaño y la distribución de plantas industriales en grandes espacios geográficos (Oberfield et al., 2020).
Muchas cuestiones combinatoriales han sido históricamente consideradas aisladamente, dando una solución adecuada a un problema que surge en algún contexto matemático. A finales del , sin embargo, se desarrollaron métodos teóricos poderosos y generales, convirtiendo la combinatoria en una rama independiente de las matemáticas por derecho propio. Una de las partes más antiguas y accesibles de la combinatoria es la teoría de grafos, que también tiene numerosas conexiones naturales a otras áreas. La combinatoria se utiliza con frecuencia en informática para obtener fórmulas y estimaciones en el análisis de algoritmos.
Combinatoria derecha|300px Para saber qué caso de combinatoria estamos tratando hay que determinar tres características: Si influye o no el orden de los elementos. Si el número de elementos disponibles en el conjunto: n, es igual o distinto de los presentes en cada suceso: r. Si se producen o no repeticiones en el suceso. derecha|300px Ver el diagrama de la derecha. Se pueden diferenciar: P: Permutaciones sin repetición. V: Variaciones sin repetición. C: Combinaciones sin repetición. PR: Permutaciones con repetición. VR: Variaciones con repetición. CR: Combinaciones con repetición.
Combinatoria sin repetición La combinatoria estudia tres tipos de casos con elementos finitos: permutaciones, variaciones y combinaciones en este caso sin repetición, dado que cada elemento solo puede aparecer una sola vez en cada evento.
Veamos estos casos:
Permutaciones sin repetición Las permutaciones de n elementos son las posibles ordenaciones de un conjunto de n elementos distintos.
Su número:
(se lee “factorial de n”). Por convenio 0!=1
En la calculadora: con la tecla x! se calcula “factorial de x” , siendo x un número entero no negativo.
Ejemplo: ¿Cuántos números de 4 cifras distintas pueden escribirse con los dígitos 2, 3 , 5 y 8?
Solución:
Hay 24 números y son:
Variaciones sin repetición Las variaciones de n elementos tomados de r en r : posibles muestras ordenadas de r elementos distintos que se pueden extraer de un conjunto de n elementos, siendo .
Su número:
(r factores enteros consecutivos decrecientes a partir de n)
En la calculadora: con la tecla nPr se calcula: : .
Notemos que:
Ejemplo:
En una carrera con 6 atletas, ¿de cuántas formas distintas podrían repartirse las medallas de oro y plata?
Solución:
formas distintas y serían, numerando los dorsales del 1 al 6 y señalando primero el oro y segundo la plata:
Combinaciones sin repetición Las combinaciones de n elementos tomados de r en r: posibles muestras sin orden de r elementos distintos que se pueden extraer de un conjunto de n elementos .
El número de combinaciones de r elementos de un conjunto de n viene dado por el coeficiente binomial:
En la calculadora: con la tecla nCr se calcula (que se lee “n sobre r”)
Ejemplo:
En una reunión de 8 personas debe nombrarse una comisión formada por dos de ellas. ¿Cuántas comisiones distintas podrían nombrarse?
Solución:
comisiones distintas y serían estas, numerando a las personas del 1 al 8:
Combinatoria con repetición La combinatoria con repetición estudia los casos de combinatoria en los que algunos elementos pueden aparecer más de una vez en un evento, como en el caso anterior se pueden ver: permutaciones, variaciones y combinaciones:
Veamos estos casos:
Permutaciones con repetición Las permutaciones con repetición son las posibles ordenaciones de una secuencia de n signos entre los que hay algunos repetidos (uno se repite x veces, otro y veces, otro z veces… etc.).
Su número:
Notemos que:
Ejemplo: ¿Cuántos números distintos de 6 cifras se pueden escribir usando tres unos, dos cincos y un ocho?
Solución:
números distintos y son:
Variaciones con repetición Las variaciones con repetición de n elementos tomados de r en r: posibles muestras ordenadas de r elementos no necesariamente distintos que se pueden extraer de un conjunto de n elementos.
Su número:
Notemos que aquí puede ser r > n
Ejemplo: ¿Cuántos números distintos de 3 cifras se escriben usando solamente las cifras 1, 2, 5 y 8 ?
Solución:
números distintos y son:
Combinaciones con repetición Las combinaciones con repetición de n elementos tomados de r en r: posibles muestras no ordenadas de r elementos no necesariamente distintos que se pueden extraer de un conjunto de n elementos.
Su número:
Notemos que aquí puede ser r > n
Ejemplo: Un banco ofrece un regalo a elegir entre 5 posibles regalos por cada cartilla. Un señor que tiene tres cartillas en dicho banco ¿de cuántas formas puede elegir el lote de tres obsequios si no le importa repetir regalos?
Solución:
lotes distintos y son:
Historia
Los conceptos básicos sobre la combinatoria y los resultados enumerativos han aparecido a lo largo del mundo antiguo. En el a. C., en la antigua India, el médico Sushruta asegura en el Susruta-samhita que es posible formar 63 combinaciones a partir de 6 sabores distintos, tomados de uno en uno, de dos en dos, etc., así calculando todas las 26 − 1 posibilidades. El historiador griego Plutarco debatió con Crisipo de Solos ( a. C.) e Hiparco de Nicea ( a. C.) sobre un problema enumerativo un tanto delicado, el cual se demostró más adelante que guardaba relación con el número Schröder–Hiparcos.Stanley, Richard P.; "Hipparchus, Plutarch, Schröder, and Hough", American Mathematical Monthly 104 (1997), num. 4, 344–350.Habsieger, Laurent; Kazarian, Maxim; y Lando, Sergei; "On the Second Number of Plutarch", American Mathematical Monthly 105 (1998), num. 5, 446.
En la Edad Media, la combinatoria continuó siendo estudiada, sobre todo fuera de la civilización Europea. El matemático indio Mahāvīra (c. 850) acuñó una fórmula para el número de permutaciones y combinaciones, y es posible que estas fórmulas ya resultaran familiares a los matemáticos indios a principios del d. C. El filósofo y astrónomo Rabbi Abraham ibn Ezra (c. 1140) estableció la simetría de los coeficientes binomiales, mientras que una fórmula concreta fue hallada más adelante por el talmudista y matemático Gersónides, en 1321.. (Traducción de la edición Rusa de 1967) El triángulo aritmético —un diagrama gráfico mostrando las relaciones entre los coeficientes binomiales— ya había aparecido en tratados matemáticos tan atrás como el , y con el tiempo serían mejor conocidos como el Triángulo de Pascal.
Durante el Renacimiento, junto al resto de las matemáticas y las ciencias, la combinatoria disfrutó de un renacer. Trabajos de Pascal, Newton, Jacob Bernoulli y Euler se volvieron fundamentales en el emergente campo. En los tiempos modernos, los trabajos de J. J. Sylvester (a finales del ) y Percy MacMahon (a principios del ) ayudaron a asentar las bases para la combinatoria enumerativa y combinatoria algebraica. La teoría de grafos también disfrutó de una explosión de interés al mismo tiempo, en especial conexión con el teorema de los cuatro colores.
En la segunda mitad del , la combinatoria sufrió un crecimiento rápido, que llevó al establecimiento de docenas de nuevos diarios y conferencias sobre este tema.Véase Journals in Combinatorics and Graph Theory En parte, el crecimiento fue estimulado por las nuevas conexiones y aplicaciones en otros campos, desde álgebra hasta probabilidades, desde el análisis funcional a la teoría de números, etc. Estas conexiones terminaron por romper los bordes entre la combinatoria y partes de la matemática y la informática teórica, pero al mismo tiempo causó cierta fragmentación dentro del campo.
Áreas de la combinatoria No existe una clasificación tajante de lo que constituye una subárea, sino que todas comparten cierto grado de traslape entre sí, al igual que con otras ramas de la matemática discreta. Diferentes autores proponen varias divisiones de la combinatoria por lo que cualquier listado es meramente indicativo. Por ejemplo, algunos autores consideran la teoría de grafos como una subárea de la combinatoria, mientras que otros la consideran un área independiente.
Entre las subdivisiones más comunes se encuentran las siguientes:
Combinatoria enumerativa La combinatoria enumerativa es el área más clásica de la combinatoria y se concentra en contar el número de ciertos objetos combinatorios. Aunque contar el número de elementos en un conjunto es un problema matemático bastante amplio, muchos de los problemas que surgen en las aplicaciones tienen una descripción combinatoria relativamente simple. Los números de Fibonacci son el ejemplo básico de un problema en la combinatoria enumerativa. La forma de doce veces mayor proporciona un marco unificado para contar las permutaciones, combinaciones y particiones.
Combinatoria analítica La combinatoria analítica se refiere a la enumeración de estructuras combinatorias utilizando herramientas de análisis complejo y teoría de probabilidades. En contraste con la combinatoria enumerativa, que utiliza fórmulas combinatorias explícitas y funciones generadoras para describir los resultados, la combinatoria analítica tiene como objetivo obtener fórmulas asintóticas.
Teoría de la partición La teoría de la partición estudia diferentes problemas asintóticos y numerales relacionados con particiones enteras, y está estrechamente relacionada con las series, funciones especiales y polinomios ortogonales. Originalmente era una parte de la teoría numérica y el análisis, ahora se considera una parte de la combinatoria o un campo independiente. Incorpora el enfoque biyectivo y diversas herramientas en análisis y teoría analítica de números, y tiene conexiones con la mecánica estadística.
Teoría de grafos