Contenidos de Combinatoria
Teoría, teoremas y definiciones de combinatoria para olimpiada matemática, con dificultad calibrada por competencia — desde la Olimpíada Matemática Galega (OMG) hasta la OME y la IMO. 12 entradas disponibles.
Principios fundamentales de conteo
Las reglas de la suma y el producto, permutaciones y combinaciones: la gramática elemental de la combinatoria, sin la cual ningún argumento posterior tiene sentido.
Coeficientes binomiales: identidades y el triángulo de Pascal
El número aparece en conteo, álgebra, probabilidad y teoría de números. Sus identidades —Pascal, Vandermonde, suma alternada— son el álgebra elemental de la combinatoria.
Fundamentos de teoría de grafos
Vértices y aristas: el lenguaje más eficaz para codificar relaciones binarias. El lema del apretón de manos, los árboles y los caminos eulerianos son la base de toda la combinatoria estructural.
Principio de inclusión-exclusión
Para contar la unión de varios conjuntos hay que sumar, restar las intersecciones por pares, sumar las triples... La fórmula que convierte el solapamiento en una suma alternada exacta.
Recurrencias combinatorias: plantear, resolver, interpretar
Muchas cantidades combinatorias se entienden mejor a través de la relación que guardan consigo mismas en tamaños más pequeños. Plantear la recurrencia correcta es a menudo la mitad del problema.
Coloraciones de grafos y el polinomio cromático
¿Cuántos colores hacen falta para que ningún par de vértices vecinos comparta color? Una pregunta de apariencia recreativa que organiza la teoría estructural de grafos —y produce el célebre teorema de los cuatro colores.
Funciones generadoras
Codificar una sucesión como los coeficientes de una serie de potencias convierte problemas de conteo en manipulaciones algebraicas. Una de las ideas más fértiles de toda la combinatoria.
Números de Catalan
Caminos de Dyck, triangulaciones de polígonos, árboles binarios, expresiones bien formadas: docenas de objetos aparentemente distintos, todos contados por la misma sucesión
Números de Stirling, de Bell y particiones de conjuntos y enteros
¿De cuántas formas se reparte un conjunto en bloques no vacíos? ¿Y un entero en sumandos? Dos familias de números —Stirling y de partición— que organizan toda la combinatoria de las descomposiciones.
Teorema de Hall y emparejamientos en grafos bipartitos
¿Cuándo se puede asignar a cada persona un trabajo distinto de entre los que sabe hacer? La condición de Hall —simple de enunciar, profunda en sus consecuencias— responde exactamente a esta pregunta.
Teoría extremal de conjuntos: Sperner, Erdős–Ko–Rado y cadenas
¿Cuántos subconjuntos de se pueden elegir sin que ninguno contenga a otro? ¿Y sin que dos sean disjuntos? Preguntas de apariencia inocente cuyas respuestas exactas son joyas de la combinatoria del siglo XX.
Teoría de Ramsey: el orden es inevitable
En cualquier conjunto suficientemente grande, por caótico que parezca, siempre emerge una estructura ordenada. La afirmación precisa de esta idea —y su demostración— es uno de los resultados más influyentes de la combinatoria del siglo XX.