Según la Wikipedia (en inglés), la expresión explosión combinatoria describe el efecto de funciones que crecen muy rápidamente como resultado de consideraciones combinatorias. En este vídeo vamos a ver un ejemplo muy descriptivo de este concepto.

La cuestión es sencilla: trata simplemente de contar los caminos mediante los que podemos llegar desde vértice superior izquierdo hasta el inferior derecho en una cuadrícula dependiendo de la complejidad de dicha cuadrícula. Vamos a ver algún ejemplo.

Si la cuadrícula tiene un único cuadrado, como ésta

¿cuántos caminos distintos pueden escogerse para llegar de A a B? Pues claramente dos, ¿verdad? Son estos:

Bien, ¿y si ahora tenemos una cuadrícula con 4 cuadrados como ésta?

¿Cuántas formas distintas habría ahora de llegar del punto A al punto B? Pues exactamente son 12, las siguientes:

Y podríamos continuar preguntándonos cómo iría creciendo ese número de caminos conforme aumentamos el tamaño de la cuadrícula. Por ejemplo, con 9 cuadrados

el número de caminos pasa a ser 184. Gran salto en número…y en tiempo de cálculo, claro está.

Para ver cuántos caminos tendríamos para una cuadrícula mayor que ésta os recomiendo que le echéis un ojo al vídeo:

Por cierto, la sucesión formada por estos números de caminos es la A007764 en la OEIS.


Vía la cuenta de Twitter de @mezvan. Si todavía no lo sigues ya estás tardando.

Print Friendly, PDF & Email