Fundamentos de la Combinatoria

Aspectos de la Combinatoria

• La combinatoria se encarga de contar estructuras de un tipo y tamaño dado (combinatoria enumerativa).
• También decide cuándo se pueden cumplir ciertos criterios.
• Se dedica a construir y analizar objetos que cumplan dichos criterios.
• Busca objetos "más grandes" o "más pequeños".
• Analiza estructuras combinatorias en un contexto algebraico.
• Aplica técnicas algebraicas a problemas combinatorios (combinatoria algebraica).
• Métodos teóricos generales han convertido a la combinatoria en una rama independiente de las matemáticas.
• La teoría de grafos es una parte antigua y accesible de la combinatoria, conectada con otras áreas.
• En informática, la combinatoria se utiliza para obtener fórmulas y estimaciones en el análisis de algoritmos.
• Estudia combinaciones, variaciones y permutaciones con elementos finitos sin repetición.

Combinatoria sin Repetición

• Cada elemento aparece una sola vez en cada evento.

Ejemplos

• Comisiones distintas numerando personas del 1 al 8. Se muestran 28 posibles comisiones de dos personas.
• En una competencia con 6 dorsales, se otorgan premios de oro y plata. Se muestran 30 posibles combinaciones.
• Números de 4 cifras distintas formados con los dígitos 2, 3, 5 y 8. Hay 24 números posibles.

Combinatoria con Repetición

• Algunos elementos pueden aparecer más de una vez en un evento.
• Se pueden observar combinaciones, variaciones y permutaciones.
• Es posible que r (el número de elementos a seleccionar) sea mayor que n (el número total de elementos).

Ejemplos

• Un banco ofrece elegir entre 5 regalos por cartilla. Con tres cartillas, un cliente tiene 35 formas de elegir regalos, pudiendo repetir.
• Números de tres cifras usando 1, 2, 5 y 8, permitiendo repetición. Hay 64 números posibles.
• Posibles combinaciones de cifras con repetición. Se listan ejemplos de combinaciones de los números 1, 5, 8 de seis dígitos.

Historia de la Combinatoria

• Conceptos básicos y resultados enumerativos surgieron en el mundo antiguo.
• En la antigua India (siglo VI a. C.), Sushruta menciona 63 combinaciones posibles de 6 sabores distintos.
• Matemático indio Mahāvīra (c. 850) formuló el número de permutaciones y combinaciones.
• Filósofo y astrónomo Rabbi Abraham ibn Ezra (c. 1140) estableció la simetría de los coeficientes binomiales.
• El triángulo aritmético apareció en el siglo X y se conoció como el Triángulo de Pascal.
• En el Renacimiento, Pascal, Newton, Jacob Bernoulli y Euler realizaron trabajos fundamentales.
• Los trabajos de J. J. Sylvester y Percy MacMahon ayudaron a establecer la combinatoria enumerativa y algebraica.
• La teoría de grafos experimentó un auge de interés, especialmente en relación con el teorema de los cuatro colores.
• En la segunda mitad del siglo XX, la combinatoria creció rápidamente, estableciendo nuevos diarios y conferencias.
• Este crecimiento fue impulsado por conexiones con otros campos como álgebra, probabilidades, análisis funcional y teoría de números.

Subdivisiones de la Combinatoria

• No existe una clasificación tajante, pero comparten cierto grado de traslape entre sí.
• Algunos autores consideran la teoría de grafos como una subárea, mientras que otros la ven como independiente.
• Entre las subdivisiones más comunes se encuentran:
  • Combinatoria enumerativa
  • Teoría de la partición
  • Teoría de grafos
  • Teoría del diseño
  • Geometría finita
  • Teoría del matroide
  • Combinatoria extrema
  • Combinatoria probabilística
  • Combinatoria algebraica
  • Combinatoria de palabras
  • Combinatoria geométrica
  • Combinatoria aritmética
  • Combinatoria infinita

Combinatoria Enumerativa

• Se enfoca en contar el número de ciertos objetos combinatorios.
• Muchos problemas tienen una descripción combinatoria simple.
• Los números de Fibonacci son un ejemplo básico.
• La forma de doce veces mayor proporciona un marco unificado para contar permutaciones, combinaciones y particiones.

Teoría de la Partición

• Estudia problemas asintóticos y numerales relacionados con particiones enteras.
• Está estrechamente relacionada con series, funciones especiales y polinomios ortogonales.
• Tiene conexiones con la mecánica estadística.

Teoría de Grafos

• Los grafos son objetos básicos en la combinatoria.
• Incluye preguntas de conteo, estructurales y algebraicas sobre grafos.
• Los métodos combinatorios se aplican a muchos problemas de teoría de grafos.
• Ambos se utilizan para buscar soluciones a diferentes problemas.

Teoría del Diseño

• Es un estudio de diseños combinatorios, colecciones de subconjuntos con ciertas propiedades de intersección.
• Los diseños de bloques son diseños combinatorios de un tipo especial.
• Tiene conexiones con la teoría de la codificación y la combinatoria geométrica.

Geometría Finita

• Es el estudio de sistemas geométricos con un número finito de puntos.
• Estudia estructuras análogas a las de geometrías continuas definidas combinatorialmente.
• Proporciona una fuente de ejemplos para la teoría del diseño.

Teoría del Matroide

• Abstrae parte de la geometría y estudia las propiedades de conjuntos de vectores.
• Fue introducida por Hassler Whitney y estudiada como parte de la teoría del orden.

Combinatoria Extrema

• Estudia preguntas extremas sobre los sistemas de conjuntos.
• Aborda preguntas sobre el mayor grafo posible que satisface ciertas propiedades.
• La teoría de Ramsey es otra parte de la combinatoria extrema, indicando que cualquier configuración suficientemente grande contendrá algún tipo de orden.

Combinatoria Probabilística

• Las preguntas son sobre la probabilidad de una cierta propiedad para un objeto aleatorio discreto, como un grafo al azar.
• Los métodos probabilísticos se utilizan para determinar la existencia de objetos combinatorios con ciertas propiedades.
• El método probabilístico demostró ser altamente eficaz en aplicaciones a la combinatoria extremal y a la teoría de los grafos.
• Un área relacionada es el estudio de cadenas de Markov finitas, especialmente en objetos combinatorios.

Combinatoria Algebraica

• Emplea métodos de álgebra abstracta en contextos combinatorios.
• Aplica técnicas combinatorias a problemas en álgebra.
• La interacción de métodos combinatorios y algebraicos es particularmente fuerte y significativa.

Combinatoria de Palabras

• Trata de lenguajes formales.
• Se plantea de forma independiente dentro de varias ramas de las matemáticas, incluyendo la teoría de números, la teoría de grupos y la probabilidad.
• Tiene aplicaciones a la combinatoria enumerativa, al análisis fractal, a la informática teórica, a la teoría de los autómatas y a la lingüística.

Combinatoria Geométrica

• Está relacionada con la geometría convexa y discreta, en particular la combinatoria poliédrica.
• Se pregunta cuántas caras de cada dimensión puede tener un politopo convexo.
• Las propiedades métricas de los politopos juegan también un papel importante.

Combinatoria Aritmética

• Surgió de la interacción entre la teoría numérica, la combinatoria, la teoría ergódica y el análisis armónico.
• Se trata de estimaciones combinatorias asociadas con operaciones aritméticas.
• La combinatoria aditiva se refiere al caso especial cuando solo están involucradas las operaciones de suma y resta.

Combinatoria Infinita

• Es una extensión de ideas en combinatoria a conjuntos infinitos.
• Es una parte de la teoría de conjuntos, utilizando herramientas e ideas tanto de la teoría de conjuntos como de la combinatoria extrema.

Combinatoria de Conjuntos

• Estudia las ordenaciones o agrupaciones de un determinado número de elementos mediante diagramas y operaciones basadas en la teoría de conjuntos.
• Fue una de las primeras áreas de la combinatoria en ser desarrollada.

Conceptos Clave en Problemas Combinatorios

• Los tipos de la muestra se determinan por dos aspectos.

Diagrama de Coordenadas

• Ejemplo de cálculo de formas de obtener 8 al tirar un par de dados, mostrando 5 formas posibles.
• Se puede encontrar el resultado f(k) para cualquier suma k: f(2)=1, f(3)=2, ..., f(12)=1.
• Representa una sucesión de valores mediante un solo objeto algebraico (un polinomio).
• Un caso particular del método de funciones generadoras, donde una serie de potencias representa valores de una sucesión.

Técnicas y Métodos

• La combinatoria enumerativa estudia las técnicas y métodos para resolver problemas cuando el número de elementos es arbitrario.
• Se busca determinar qué tan grande o pequeña debe ser una colección de objetos para que satisfaga una condición previamente establecida.

Combinatoria Extrema

• Se pregunta sobre qué tan grande puede hacerse un listado de forma que cualquier pareja de subconjuntos tenga un elemento en común.
• Si el conjunto original tiene n elementos, entonces el listado puede tener como máximo 2^(n-1) subconjuntos.

Optimización Combinatoria

• Es el estudio de la optimización de objetos discretos y combinatorios.
• Comenzó como parte de la teoría combinatoria y la teoría de grafos.
• Ahora se ve como una rama de la matemática aplicada y la informática.

Teoría de la Codificación

• Comenzó como parte de la teoría del diseño con construcciones combinatoriales tempranas de códigos correctores de errores.
• La idea principal es diseñar métodos eficientes y confiables de transmisión de datos.

Geometría Discreta

• Comenzó como una parte de la combinatoria, con resultados tempranos en politopos convexos y "números cercanos".
• Con la aparición de aplicaciones a la geometría computacional, se fusionaron parcialmente en un campo independiente.

Interacciones con la Física

• Hay interacciones crecientes entre la combinatoria y la física, particularmente la física estadística.
• Ejemplos incluyen una solución exacta del modelo de Ising y una conexión entre el modelo de Potts y los polinomios cromáticos y de Tutte.

Principio de Inclusión-Exclusión

• Se puede demostrar por inducción sobre el número de conjuntos.
• Enunciado de la siguiente manera usando operaciones de conjuntos.
• Desarrollo análogo para el cubo de un binomio.

Fórmula del Binomio de Newton

• Generaliza lo anterior al desarrollo de cualquier potencia natural de un binomio.
• Para cualesquiera números a, b ∈ R y cualquier número n ∈ N.
• Demostración por inducción respecto de n.

Principio Multiplicativo

• Si se desea realizar una actividad que consta de r pasos, donde el primer paso puede ser llevado a cabo de N1 maneras, etc.
• Esta actividad puede ser llevada a efecto de N1 * N2 * ... * Nr maneras.
• Cada uno de los pasos de la actividad deben ser llevados a efecto, uno tras otro.
• El total de maneras distintas en que puede suceder el evento "ocurren E1 y E2….. y Ep" es igual a producto.

Ejemplo

• Se dispone de 3 vías para viajar de C1 a C2 y de 4 vías para viajar de C2 a C1.
• ¿De cuántas formas se puede organizar el viaje de ida y vuelta de C1 a C2?
• Respuesta: (3)(4)=12

Principio Aditivo

• Si se desea llevar a efecto una actividad con formas alternativas, donde la primera alternativa puede ser realizada de M maneras.
• Esa actividad puede ser llevada a cabo de, M + N +.........+ W maneras.

Ejemplo

• Una persona desea comprar una lavadora de ropa, pensando en marcas Whirlpool, Easy y General Electric.
• Se describe la variedad de modelos y características de cada marca.
• Se pregunta de cuántas maneras tiene esta persona de comprar una lavadora.

Ejemplo

• Una pareja ofrece modelos de vivienda en dos fraccionamientos: Lomas de la Presa y Playas.
• Presa ofrece un modelo económico o un condominio.
• Playas ofrece un modelo económico, residencial, californiano y provenzal.
• ¿Cuántas alternativas diferentes de vivienda le ofrecen a la pareja?

Permutación

• Es un arreglo o posición de r objetos seleccionados de un solo grupo de n objetos posibles.
• Los arreglos a, b, c y b, a, c son permutaciones diferentes.
• La fórmula para contar el número total de permutaciones distintas es: nPr = n!/(n - r)!

Ejemplo

• Aplicando la fórmula de la permutación nPr = n!/(n - r)!
• 15P4 = 15! / (15-4)! = 15! / 11! = 32760

Combinación

• Es el número de formas de seleccionar r objetos de un grupo de n objetos sin importar el orden.
• La fórmula de combinaciones es: nCr = n! / [r!(n – r)!]

Ejemplo

• En una compañía se quiere establecer un código de colores para identificar cada una de las 42 partes de un producto.
• Se quiere marcar con 3 colores de un total de 7 cada una de las partes, de tal suerte que cada una tenga una combinación de 3 colores diferentes.
• nCr = 7! / [3!(7-3)!] = 5040 / (6*24) = 35