En matemáticas, una explosión combinatoria consiste en el crecimiento muy rápido de la complejidad de un problema debido a cómo se ve afectado por las condiciones iniciales, restricciones y límites del propio problema.
La explosión combinatoria se utiliza a veces para justificar la intrazabilidad de ciertos problemas.
La sucesión A002860 del índice OEIS es un ejemplo de explosión combinatoria, en relación con los cuadrados latinos.
Viene ilustrado por la siguiente tabla: También ocurren explosiones combinatorias en algunos puzles dispuestos en forma matricial, como los sudokus.
La explosión combinatoria aparece a medida que aumenta n, creando límites prácticos a las propiedades de los sudokus que se pueden construir, analizar y solucionar, como se muestra en la siguiente tabla: Un ejemplo en un juego donde la complejidad combinatoria conduce a un límite para su solución es el es en solucionar ajedrez (un juego con 64 plazas y 32 piezas).
Como ejemplo valga una taxonomía donde diferentes verduras reciben la herencia de sus ancestros.