El problema de Catalan

El problema de Catalan consiste en determinar el número de formas Cn en que se puede calcular el producto de n factores ordenados, realizando las operaciones por parejas.

Por ejemplo, si n=4, el producto abcd puede calcularse de las siguientes cinco formas:

  • [(a\cdot b)\cdot c]\cdot d,
  • [a\cdot(b\cdot c)]\cdot d,
  • (a\cdot b)\cdot(c\cdot d),
  • a\cdot [b\cdot(c\cdot d)],
  • a\cdot[(b\cdot c)\cdot d].

Hay un bonito artículo en Wikipedia explicando cómo obtener una relación recursiva para calcular estos números:

C_n=\sum_{k=1}^{n-1} C_k C_{n-k}.

Que, como todos ya sabemos, es la recurrencia que genera los números de Catalan.

Ahora, es común definir los números de Catalan como el número de formas de recorrer una cuadrícula de n×n partiendo de la coordenada (0,0) hasta la (n,n) de manera que los movimientos permitidos sean a la derecha y hacia arriba y no se permite cruzar la diagonal. Por ejemplo

Media_httpuploadwikim_arnkk

(Imagen de Wikimedia Commons)

son las C4=14 formas de recorrer la cuadrícula de 4×4.

El problema planteado aquí es: establece una correspondencia entre las formas de poner paréntesis a n factores y las formas de recorrer la cuadrícula de n×n siguiendo las reglas mencionadas.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s