(Vídeo) Un ejemplo de explosión combinatoria

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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

11 Comentarios

  1. Esta Excelente este Video y más la información, me gusto ya que me inclino por la matemática aplicada. lo Máximo lo compartire

    Publica una respuesta
  2. Con los valores conocidos de la serie parece que tiene una ley de crecimiento parecido al de la función a(n) = 10^((n/2)^2)

    Publica una respuesta
  3. Muy buen vídeo. Con ese toque oriental que tanto apasiona (y desorienta) a occidente. Un detalle que me llama la atención es que en el vídeo la lectura de los números es en grupos de cuatro cifras, en vez de tres.

    Publica una respuesta
  4. Muy interesante para un ejercicio de programación, he posteado en Solveet.

    Por otra parte, en A007764 comentan:

    “Daniel Forgues, Jan 03 2011 (Start) For n=14, there exists at least one Hamiltonian path from (0,0) to (14,14). For which n do we have at least one Hamiltonian path?”

    Sin embargo, parece obvio que para N impar siempre existe un camino de Hamilton (sin mas que zizaguear).

    ¿Qué no estoy viendo? ¡Gracias!

    Publica una respuesta
  5. Hace muchos años, creo que en 1º de carrera, me pusieron un problema en un examen relacionado con este tema, pero limitando el Nº de caminos a diferentes caminos de longitud mínima.

    Era una ciudad rectangular 9*6 y había que calcular cuantos caminos mínimos existian.

    Con esta limitación el resultado disminuía drásticamente a 84

    Publica una respuesta
  6. @Luis, el dibujo que indicas tiene nodos impares (pero es culpa mía, usé “N impar” incorrectamente) y se resuelve simplemente zizgagueando.

    Me refería a que Daniel (en oeis.org) pregunta:

    “For which n do we have at least one Hamiltonian path?”

    Él (Daniel) está presentando un caso con nº de nodos impar (N cuadros par), pero es trivial ver que para cualquier cuadrícula de nodos impares (N cuadros pares) hay un camino de hamilton.

    Publica una respuesta
  7. Ah perdon, lo interprete como cantidad de cuadrados.
    No se porque me confundi y pense que en la cantidad de cuadrados impar se podia hacer el zigzag normal y aca tenia que cambiarlo y hacer uno mas rebuscado.

    Publica una respuesta
  8. Al final, por donde esta la solucion del problema…

    Hay alguna manera de contar los caminos que no sea uno por uno o con computadoras????

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Según la Wikipedia (en inglés), la expresión explosión combinatoria describe el efecto de funciones…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *