Sigue esta ruta para aprender combinatoria de manera progresiva. Los temas están ordenados por dificultad.
El estudio del conteo, los arreglos y las estructuras discretas.
Principios y técnicas fundamentales para contar.
Si los eventos A y B son ajenos, |A ∪ B| = |A| + |B|.
Si A tiene m opciones y B tiene n, el total es m × n.
Sumar las posibilidades cuando los casos no se traslapan.
Multiplicar las opciones que hay en cada paso.
Usar diagramas de árbol para contar paso a paso.
Arreglos ordenados: hay n! formas de ordenar n objetos.
Selecciones sin orden: C(n,k) = n!/(k!(n-k)!).
Demuestra que algo tiene que existir.
La regla C(n,k) = C(n-1,k-1) + C(n-1,k).
La regla |A∪B| = |A| + |B| - |A∩B|.
Usar la fórmula n!/(k!(n-k)!).
La regla F(n) = F(n-1) + F(n-2).
Elegir a k personas de un grupo de n.
Meter n+1 objetos en n cajas.
Restar los casos que no queremos del total.
Problemas con diagramas de Venn.
La propiedad C(n,k) = C(n,n-k).
La suma de la fila n siempre es 2^n.
Usa 2^n y combinaciones para hallar subconjuntos.
Propiedades e identidades de C(n,k).
Si metes n+1 objetos en n casillas, alguna tendrá al menos 2.
|A ∪ B| = |A| + |B| - |A ∩ B|.
(x + y)ⁿ = Σ C(n,k) xᵏ yⁿ⁻ᵏ.
Aplicación directa: n+1 palomas en n nidos.
Fₙ = Fₙ₋₁ + Fₙ₋₂, útil para contar pavimentaciones y otras estructuras.
C(n,k) = C(n-1,k-1) + C(n-1,k).
Expande (a + b)^n usando coeficientes.
n!/(n₁!n₂!...nₖ!) para conjuntos con elementos repetidos.
Ver quién gana si ambos juegan perfecto.
Soluciones de x1+x2+...+xk = n con xi ≥ 1.
Suma alternada para n conjuntos.
n objetos en k cajas implica ⌈n/k⌉ en una.
Condiciones para caminos y circuitos eulerianos.
La paridad se mantiene tras las operaciones.
Usar colores para problemas de pavimentación.
Pavimentar cuando falta un cuadrito.
Variantes del problema del cumpleaños.
Clasificar los estados del juego.
Invariantes de suma o conteo de paridad.
Encuentra el k-ésimo término de una expansión.
Probar que algo es imposible usando colores.
La suma total se mantiene igual.
Soluciones donde xi ≥ 0.
(n-1)! formas de acomodar n objetos en un círculo.
Evalúa sumas como C(n,0)+C(n,1)+...
Problemas de mosaicos y composiciones.
Todos los vértices deben tener grado par.
Imposibilidad al quitar esquinas opuestas.
Tableros de 2×n con dominós.
Cuando la suma de las paridades no cambia.
Formas de escribir n como suma de 1s y 2s.
F₁ + F₂ + ... + Fₙ = F(n+2) - 1.
Exactamente 0 o 2 vértices de grado impar.
χ(G) = 2 si y solo si es bipartito.
Cada dominó cubre un cuadro de cada color.
Usar cuadritos blancos y negros.
Estrellas y barras, particiones y números de Stirling.
Conteo usando |A ∪ B| = |A| + |B| - |A ∩ B| y sus generalizaciones.
El estudio de los vértices y las aristas.
Contar lo mismo de dos formas para obtener identidades.
Juegos combinatorios para dos jugadores.
Cantidades que no cambian al aplicar operaciones.
Cubrir regiones usando figuras específicas.
Cubrir regiones con rectángulos de 1×2.
Vértices, aristas, grados, caminos y ciclos.
Repartir n objetos idénticos en k cajas distintas: C(n+k-1,k-1).
Usar propiedades par/impar que se mantienen constantes.
Posiciones ganadoras y perdedoras, robo de estrategia y emparejamiento.
Si hay n objetos en k cajas, alguna tiene al menos ⌈n/k⌉ objetos.
Usar dos colores para probar que un teselado es imposible.
Usar coloraciones para demostrar que algo es imposible.
Σ C(i,r) desde i=r hasta n = C(n+1,r+1).
Suma de elementos en diagonal (palo de hockey).
Problema de la fiesta: 6 personas, amigos o extraños.
Calcular el XOR de los tamaños de las pilas.
Cantidades que no cambian módulo k.
El mínimo de colores necesarios.
Argumentos de paridad usando dos colores.
La suma de los grados es 2|E| (lema del apretón de manos).
Probar que la estrategia greedy es la mejor.
La fórmula Dn = n!(1 - 1/1! + 1/2! - ...).
La expresión Cn = C(2n,n)/(n+1).
Usar múltiples colores para encontrar invariantes.
Usa esta regla en problemas de sumatorias.
Caminos que no cruzan la diagonal.
Gráficas conexas sin ciclos: n vértices y n-1 aristas.
La notación !n y sus propiedades.
Algoritmos de Fleury y Hierholzer.
Grafos planos necesitan máximo 4 colores.
Forma cerrada usando la proporción áurea.
Moverse para que el XOR sea cero.
Funciones sobreyectivas usando inclusión-exclusión.
Soluciones con límites superiores o inferiores.
El problema de los sombreros y similares.
Identidad de Cassini y fórmulas de suma.
Cuenta formas válidas de poner paréntesis.
Sumas con signos que se van alternando.
χ(G) ≤ Δ(G) + 1.
Principio de las casillas en aristas desde un vértice.
Obteniendo Cn = C(2n,n)/(n+1).
El candidato A siempre va adelante del B.
F(n-1)F(n+1) - F(n)² = (-1)ⁿ.
φ = (1+√5)/2 y sus propiedades.
XOR como suma binaria sin acarreo.
Permutaciones pares contra impares.
Alternar colores para checar la paridad.
D_n ≈ n!/e.
Caminos de (0,0) a (2n,0) por encima del eje x.
Contraejemplo de 5 vértices.
Cn = Σ Ci·C(n-1-i).
D_n = (n-1)(D_{n-1} + D_{n-2}).
El XOR de los tamaños de las pilas.
Subconjuntos sin elementos consecutivos.
F_m divide a F_mn.
Números de Catalan, Fibonacci y otras sucesiones combinatorias.
Usar elementos máximos o mínimos para armar argumentos.
Cantidades que solo aumentan o solo disminuyen al operar.
Construcciones voraces, inductivas y recursivas.
Cₙ = C(2n,n)/(n+1), cuentan caminos de Dyck, paréntesis válidos, etc.
Tomar la mejor opción local en cada paso.
|A₁ ∪ ... ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ ∩ Aⱼ| + ... + (-1)ⁿ⁺¹|A₁ ∩ ... ∩ Aₙ|.
Clases de residuos que se conservan tras las operaciones.
El juego clásico con estrategia basada en XOR.
Formas de escribir n como suma de enteros positivos.
Caminos que pasan por cada arista una sola vez. Existen si hay 0 o 2 vértices impares.
Caminos que pasan por cada vértice exactamente una vez.
Permutaciones sin puntos fijos: Dₙ = n!(1 - 1/1! + 1/2! - ... + (-1)ⁿ/n!).
C(m+n,r) = Σ C(m,k)C(n,r-k).
Colorear vértices de modo que los que estén unidos tengan colores distintos.
Gráficas que se pueden dibujar en el plano sin que se crucen las aristas.
SG(posición) = mex de los sucesores.
V - E + F = 2 para gráficas planas conexas.
Codifica sucesiones como series de potencias.
Particiones en partes distintas o limitadas.
Suma de C(m,k)C(n,r-k) = C(m+n,r).
Teoremas de Dirac y Ore.
Toda sucesión de mn+1 tiene una de n+1 monótona.
Usa la identidad en problemas de conteo.
Cuenta particiones de conjuntos.
El SG del juego combinado es el XOR.
Matrices de transferencia y recursiones.
Producto, derivada y extracción de coeficientes.
Colorear aristas para que no choquen.
Cuenta cuántos árboles binarios hay con n nodos.
Vértices divididos en dos conjuntos con aristas solo entre ellos.
Pasar de recurrencias a una fórmula cerrada.
Funciones sobreyectivas n! × S(m,n).
Cada nodo tiene 0 o 2 hijos.
1/(1-x), 1/(1-x)², etc.
Convolución de sucesiones.
Resolver an = c₁a(n-1) + c₂a(n-2) + ...
El entero no negativo más pequeño que no está en el conjunto.
Calcular el valor SG para juegos sencillos.
De una recurrencia a una función racional.
xA'(x) desplaza y multiplica por n.
El orden de los hijos importa.
[[1,1],[1,0]]ⁿ nos da los números de Fibonacci.
S(m,n) cuenta las particiones de un conjunto.
Las raíces nos dan la forma cerrada.
mcd(F_m, F_n) = F_mcd(m,n).
Técnicas para hallar [xⁿ]A(x).
Contar caminos 'malos' usando reflexión.
Codificar sucesiones como coeficientes de series de potencias.
A(x) = Σaₙxⁿ para contar sucesiones.
Cualquier sucesión de mn+1 números tiene una subsucesión monótona de largo m+1 o n+1.
1ra clase: permutaciones con k ciclos. 2da clase: particiones en k subconjuntos.
Cualquier juego imparcial equivale a un montón de Nim.
C(m,n) mod p = Π C(mᵢ,nᵢ) mod p, usando m y n en base p.
Conjunto de aristas que no comparten ningún vértice.
Estructuras garantizadas en gráficas coloreadas muy grandes. R(3,3) = 6.
Calcula C(n,k) módulo un primo p.
Una gráfica bipartita tiene emparejamiento perfecto si |N(S)| ≥ |S| para todo S.
Usar coeficientes de la forma x^n/n!.
Cuenta permutaciones según sus ciclos.
Usa Lucas para temas de divisibilidad.
Usa funciones generatrices para particiones.
FGE para permutaciones y arreglos.
Cotas superiores e inferiores.
A(x) = Σaₙxⁿ/n! para estructuras etiquetadas.
Probar que algo existe usando argumentos de probabilidad.