Los números de Catalan

Este artículo es mi aportación a la primera edición de Carnaval de Matemáticas organizado por Tito Eliatron.

Motivación

Un polígono convexo es un polígono que cumple que todos sus ángulos interiores miden menos de 180º. De forma más intuitiva, un polígono es convexo cuando todos sus vértices están apuntando hacia el exterior del polígono. Por ejemplo, el siguiente polígono es convexo

Polígono convexo

pero éste no lo es

Polígono no convexo

Según esta definición es evidente que todos los polígonos regulares (triángulo equilátero, cuadrado, pentágono regular…) son convexos.

Bien, aclarado este punto vamos a realizar un experimento con estos polígonos regulares. Lo que vamos a hacer es dividir cada uno de ellos en triángulos trazando diagonales que no se corten entre si. Y vamos a contar de cuántas formas podemos hacer esa subdivisión para cada uno de los polígonos.

Tomemos el primer polígono regular en lo que a número de lados se refiere, el triángulo equilátero. Está claro que en un triángulo equilátero no se puede trazar ninguna diagonal, pero como la propia figura es un triángulo digamos que ya tendríamos el polígono dividido en triángulos. Esto es, el número de formas en las que podemos dividir un triángulo equilátero en triángulos trazando diagonales de la forma descrita antes es $1$ .

Pasamos al siguiente, el cuadrado. En él podemos trazar dos diagonales que lo dividen en triángulos

Cuadrados

Por ello, el número de formas en las que podemos dividir el cuadrado en triángulos como se comentó antes es $2$ .

El siguiente es el pentágono. En este caso cada forma de dividirlo en triángulos así consiste en trazar dos diagonales que no se corten. Estas son las $5$ formas.

Pentágonos

Con el hexágono el número de diagonales a trazar es tres por vez. Nos quedan las siguientes $14$ formas de dividir un hexágono regular como hemos dicho antes:

Hexágonos

Con un heptágono obtendríamos $42$ formas, con un octógono $132$ , y así sucesivamente…Un momento, ¿cómo que y así sucesivamente? Hemos obtenido la siguiente sucesión de números:

$1, 2, 5, 14, 42, 132, \ldots$

A la vista de estos elementos no parece que sea muy evidente cómo encontrar el siguiente término. La sucesión de números obtenida más bien parece aleatoria, casual, sin ningún interés…

La pregunta está clara:

¿Aparecen estos números en algún otro sitio? ¿Tienen algo de interés?

Pues va a ser que sí…

Los números de Catalán

Al parecer fue el gran Leonhard Euler (quién si no) el que se hizo la pregunta relacionada con los polígonos que hemos descrito antes. De hecho encontró una manera de calcular los términos de la sucesión. Si llamamos $C_n$ al n-ésimo elemento de la misma, dicha expresión es la siguiente:

$C_{n-2}=\cfrac{2 \cdot 6 \cdot \ldots \cdot (4n-10)}{(n-1)!}$ , para $n > 2$

Por ejemplo, calculemos $C_5$ (es decir, debemos tomar $n=7$ :

$C_5=\cfrac{2 \cdot 6 \cdot 10 \cdot 14 \cdot 18}{(7-1)!}=\cfrac{302140}{720}=42$

que es el quinto término de la sucesión que hemos comentado al principio.

Como esta expresión puede ser algo complicada de manejar os dejo otra más sencilla (al parecer la más sencilla que se conoce). El término $n$ de esta sucesión, $C_n$ , se puede calcular de la siguiente forma:

$C_n=\cfrac{(2n)!}{n! (n+1)!}$

Pero esta sucesión de números toma su nombre de Eugène Charles Catalan, matemático belga del que ya hablamos en este artículo. La razón es la resolución por parte de éste del siguiente problema:

Tenemos $n$ letras dispuestas en forma de palabra en un cierto orden. Deseamos añadir $n-1$ pares de paréntesis en esta palabra de forma que dentro de cada par de paréntesis caigan dos términos. Estos dos términos pueden ser dos letras juntas, una letra junto con un grupo encerrado ya entre paréntesis o dos grupos contiguos. ¿De cuántas formas podemos realizar esta tarea?

Vamos a explorar los primeros casos:

Para dos letras, $ab$ , hay sólo una forma:
$(ab)$
Para tres letras, $abc$ , tenemos dos formas:
$((ab)c)$ y $(a(bc))$
Si tenemos cuatros letras, $abcd$ , se obtienen cinco formas:
$((ab)(cd)), (((ab)c)d), (a(b(cd))), (a((bc)d))$ y $((a(bc))d)$

Obtenemos los números $1, 2$ y $5$ . Y si continuáramos obtendríamos $14, 42, \ldots$ . Esto es, la sucesión presentada en el comienzo de este artículo.

Es interesante apuntar que a veces esta sucesión se toma de la siguiente forma:

$1,1,2,5,14, 42, \ldots$

Escribiéndola de esta manera tenemos una forma muy interesante de calcular cada término si conocemos los anteriores:

Sea $k$ el último número de Catalan que conocemos y sea $n$ la posición del número siguiente en esta sucesión. Entonces dicho número se calcula mediante la siguiente expresión:

$\cfrac{k \cdot (4n-6)}{n}$

Por ejemplo, si el último término que conocemos es el 14, el siguiente es el que ocupa la sexta posición. Entonces $k=14$ y $n=6$ y el siguiente término es:

$\cfrac{14 \cdot (4 \cdot 6-6)}{6}=42$

Ya llevamos dos situaciones, en principio sin relación aparente, donde aparece esta sucesión. Pero no son los únicos. Árbol plano, plantado y trivalente Por ejemplo, Arthur Cayley demostró que los números de Catalan también nos dan el número total de árboles (Árbol: grafo conexo que no tiene circuitos) planos (Plano: se puede dibujar en un plano sin que haya intersecciones entre aristas), plantados (Plantado: tiene un tronco en cuyo extremo se haya la raíz) y trivalentes (Trivalente: en cada punto, excepto en la raíz y en extremos, se unen tres vértices). Un ejemplo de árbol de este tipo es el que aparece en la figura de la derecha.

Por cierto, es muy interesante ver gráficamente la relación existente entre las tres situaciones relacionadas con esta sucesión de números que se han mostrado hasta ahora. En esta imagen podéis ver dicha relación.

Pero, como era de esperar, estas situaciones no son las únicas con esta propiedad. Los números de Catalan aparecen en otros muchos lugares (seguro que a más de uno os recuerda a la sucesión de Fibonacci). Por poner un par de ejemplos más, esta sucesión está relacionada con un problema sobre caminos recorridos por una torre en un tablero de ajedrez y con un problema sobre uniones de puntos sobre una circunferencia con segmento que no se corten.

Y para terminar os dejo una sorprendente conexión entre estos números de Catalan y el triángulo de Pascal. Sí, exacto, los números de Catalan también están escondidos en este fabuloso triángulo. Y es sencillo encontrarlos.

Tomamos el triángulo de Pascal

Triángulo de Pascal

y nos quedamos con la columna central, esto es, $1, 2, 6, 20, \ldots$ . Ahora restamos a cada número de esa columna central el número que tiene al lado en el triángulo. Podéis comprobar que así también obtenemos los números de Catalan (no, si ya decíamos que al final iban a tener alguna relación con la sucesión de Fibonacci).

Fuente:

Viajes en el tiempo y otras perplejidades matemáticas, de Martin Gardner.

27 comentarios

Trackback | 11 Feb, 2010

Bitacoras.com
Trackback | 11 Feb, 2010

Los números de Catalan
Milhaud | 11 de February de 2010 | 19:59

Sí conocía el problema de los triangulos posibles dentro de un polígono convexo, pero no sabía que la serie resultante era una serie numérica con nombre propio.

Fascinante las relaciones que expones, y apuesto a que existen muchas más. Al final, las matemáticas son mucho más convergentes de lo que muchos creen.
Isma | 11 de February de 2010 | 21:58

Fántastico árticulo, llevo leyendo el blog desde hace un tiempo porque la verdad me apasionan las matemáticas, aunque ya he visto que hay un nivel muy alto. Hace tiempo me tope con un problemilla que se le atasco hasta a mi profesor (estoy haciendo una ingenieria) aquí os lo dejo a ver si alguno (seguro que sí) lo sabe hacer:

$A= \sum_{n=1}^{\infinity} {1 \over 2^n + 1}$

(*es hasta infinito pero no consigo que salga!)
josejuan | 12 de February de 2010 | 01:18

Ufff… ni idea, pero es interesante.

Claramente es convergente (cualquier criterio, pero fácilmente se ve que está entre $\sum_{n=1}^{\infty }2^{-n}$ y $\sum_{n=1}^{\infty }3^{-n}$ la primera vale 1 y la segunda 1/2 luego la nuestra está en medio).

No he visto ninguna serie parecida a esa (con denominador exponencial + algo), desconozco si tiene solución (fácil o no).

Quizás se puedan ir haciendo acotaciones más finas como la que pongo (numéricamente se ve sin dificultad que vale $0.764\,5$ ) y hasta usando análisis complejo pueda haber alguna solución analítica…

¿Alguien se anima?
hernan | 12 de February de 2010 | 03:54

Dudo que la serie de Isma tenga un solución simple.
Yo probé definiendo la función de variable real
$U(x) = \sum_{n=1}^\infty \frac{1}{2^n + x}$ y haciendo su expansión en Taylor en $x=0$ (sabemos su valor en x=0, nos interesa su valor en latex x=1) y llegué (con varias suposiciones no rigurosamente demostradas pero plausibles) a
$A = U(1) = \sum_{n=1}^\infty \frac{(-1)^{n+1}}{2^n -1}$ lo cual parece numéricamente correcto, pero no es más simple que la serie original (aunque esta es decreciente de signos alternados, lo que facilita algunas acotaciones – y acaso converja un poquito más rápido).
No deja de extrañarme un poco que las dos series sean equivalentes (si es que realmente lo son)… sospecho que debe haber una forma mucho más simple de verlo:

$\frac{1}{2+1} + \frac{1}{4+1} + \frac{1}{8+1} + \frac{1}{16+1} + \cdots = \frac{1}{2-1} - \frac{1}{4-1} + \frac{1}{8-1} - \frac{1}{16-1} + \cdots$

… pero yo no lo veo.
josejuan | 12 de February de 2010 | 10:42

Uhm… creo que me quedo muy cerca, pero no me salen las divisiones binarias (¡debería ser fácil!).

Tenemos el término general como

$\frac{1}{2^{n}+1}$

el denominador en binario es siempre de la forma

11
101
1001
10001
…

entonces, la inversa de dichos números son siempre de la forma (siempre en binario)

$\sum_{n=1}^{\infty }(2^{-a_{1}n}+2^{-a_{2}n}+\cdot \cdot \cdot )$

por ejemplo, el primer término (n=1) es

$\frac{1}{2^{1}+1}=\frac{1}{3}=\sum_{n=1}^{\infty }2^{-2n}=\allowbreak 0.333\,33$

entonces, hemos convertido ese horripilante denominador en una suma de denominadores bonitos y elegantes.

Ahora “sólo” queda aglutinar todos los sumandos con exponente igual y listo.

Pero no puedo seguir porque no me salen los términos generales de las divisiones binarias.

Arghhh….!
josejuan | 12 de February de 2010 | 10:45

Por ejemplo, siguiendo el método de multiplicar por dos el número decimal y ver la parte entera tenemos para 1/5=0.2 lo siguiente

0.2 x 2 = 0.4 -> 0
0.4 x 2 = 0.8 -> 0
0.8 x 2 = 1.6 -> 1
0.6 x 2 = 1.2 -> 1
0.2 x 2 … (periodo)

entonces el desarrollo debería ser

$\sum_{n=1}^{\infty }(2^{-3n}+2^{-4n})$

¡pero me da 0.20952 y no 0.2!
josejuan | 12 de February de 2010 | 12:31

¡Mecachis! claro, como que es periodo de longitud 4

$\sum_{n=1}^{\infty }2^{-4n+1}+\sum_{n=1}^{\infty }2^{-4n}$

(vaya fallo…)
josejuan | 12 de February de 2010 | 12:42

¡Ya lo tengo!

La identidad que yo buscaba es

$\frac{1}{2^{n}+1}=(2^{n}-1)\sum_{k=1}^{\infty }2^{-2k}$

ahora “sólo” queda montar el sumatorio del sumatorio…
josejuan | 12 de February de 2010 | 12:47

Perdón se me ha escapado un ‘n’

$(2^{n}-1)\sum_{k=1}^{\infty }2^{-2nk}$
josejuan | 12 de February de 2010 | 13:02

Ummfrrggrr…. muy buena pinta no tiene…

$\sum_{n=1}^{\infty }\frac{1}{2^{n}+1}\vspace{1pt}=\sum_{n=1}^{\infty }(2^{n}-1)\sum_{k=1}^{\infty }2^{-2nk}$

si intentamos quitar el factor común o intentamos calcular las subseries entonces volvemos a tener un denominador con suma ¡arghh! e intentar reducir la serie de series no parece fácil…
Isma | 12 de February de 2010 | 13:34

La gracia de este ejercicio es que un profesor particular se lo puso a un amigo con el que yo preparé mi examen de cálculo. Él me lo enseñó y me sentí muy estúpido al no saber hacerlo, por eso al día siguiente se lo llevé a mi profesor de la uni que me dijo que ni idea! Ahora ya no puedo contactar con el profesor particular y estoy muy muy intrigado. Gracias por los intentos seguro que al final sale!
hernan | 12 de February de 2010 | 16:09

Por cierto, mi identidad era fácil de obtener, con sólo la fórmula de la serie geométrica :

$\frac{1}{2^n+1} = \frac{1}{2^n} \frac{1}{1+2^{-n}}= \frac{1}{2^n} \sum_{k=0} (-1)^k 2^{- n k}$

$\sum_{n=1}\frac{1}{2^n+1} = \sum_{n=1} \sum_{k=0} (-1)^k 2^{- n (k+1)}$

$= \sum_{k=0} (-1)^k \sum_{n=1} 2^{- n (k+1)} = \sum_{k=0} \frac{(-1)^k}{2^{k+1}-1} = \sum_{k=1} \frac{(-1)^{k+1} }{2^{k}-1}$

Pero con esto no hemos progresado nada
Nicolás | 12 de February de 2010 | 21:48

Ja, ja… La suma del problema que discuten no es para nada trivial… Ya casi la tengo… (Aunque se me va a complicar ponerla en latex)
Nicolás | 12 de February de 2010 | 22:11

Lo que yo hice fue calcular el sumatorio con un valor inicial de $n=0$ en lugar de $n=1$ , y descomponer la suma parcial del mismo, con lo cual queda.

\sum_{n=0}^{m} \frac{1}{1+2^n} = \frac{{\psi}_{\frac{1}{2}}^{(0)}(-\frac{i\pi }{ln(2)})}{ln (2)} – \frac{{\psi}_{\frac{1}{2}}^{(0)}(-\frac{i\pi-ln(2)(m+1)}{ln(2)})}{ln (2)}
Nicolás | 12 de February de 2010 | 22:29

Lo que yo hice fue calcular el sumatorio con un valor inicial de $n=0$ en lugar de $n=1$ , y descomponer la suma parcial del mismo, con lo cual queda.

$\sum_{n=0}^{m} \frac{1}{1+2^n} = \frac{{\psi}_{\frac{1}{2}}^{(0)}(-\frac{i\pi }{ln(2)})}{ln (2)} - \frac{{\psi}_{\frac{1}{2}}^{(0)}(-\frac{i\pi-ln(2)(m+1)}{ln(2)})}{ln (2)}$

Donde $\psi}_{q}^{(0)}(z)$ es la función q-Digamma.
Aplicando límite a ambos lados nos queda:

$\sum_{n=0}^{ \infty} \frac{1}{1+2^n} = \frac{{\psi}_{\frac{1}{2}}^{(0)}(-\frac{i\pi }{ln(2)})}{ln (2)} - 1$

Obviamente, para nuestro caso tenemos que restar $1/2$ a la expresión anterior, con lo cual tenemos que:

$A = \frac{{\psi}_{\frac{1}{2}}^{(0)}(-\frac{i\pi }{ln(2)})}{ln (2)} - 3/2 \approx 0,7645$ . Claro que me restaría hallar una forma de simplificar el termino que contiene a la función q-poligamma (si es que esto es posible).
Isma | 12 de February de 2010 | 22:58

uff la función q-Digamma me queda muy muy lejos!intentare buscar algo a ver..
Rober | 15 de February de 2010 | 00:15

No se si tengo sitio en este margen (je je) pero los resultados en binario de cada sumando son de la forma:

0,010101010101… = 1 / (2^1 + 1)
0,001100110011… = 1 / (2^2 + 1)
0,000111000111… = 1 / (2^3 + 1)
0,000011110000… = 1 / (2^4 + 1)
0,000001111100… = 1 / (2^5 + 1)
0,000000111111… = 1 / (2^6 + 1)
0,000000011111… = 1 / (2^7 + 1)
0,000000001111… = 1 / (2^8 + 1)
0,000000000111… = 1 / (2^9 + 1)
0,000000000011… = 1 / (2^10 + 1)
0,000000000001… = 1 / (2^11+ 1)
…

Es decir, un periodo de “n” ceros seguidos de “n” unos. Se puede demostrar en cada sumando viendo que si lo multiplicamos por 2^n los unos y ceros quedan “intercalados”. Sumando ambos queda 0,1111… (un periodo de 1) lo que vale 1. Es decir que:

1/(2^n+1) + 2^n / (2^n+1) tiene que valer 1, que lo vale.

¿De qué nos sirve eso? pues ahora hay que sumar cada columna decimal. Como cada sumando añade un cero, la suma de cada columna es finita. Se ve fácilmente que la primera (1/2) vale cero y que la segunda (1/2^2) vale 1, etc. Pero hay que encontrar el término general.

Si el término general es f(n), la suma final es:

1/2^1*f(1) + 1/2^2*f(2) + 1/2^3*f(3) …

Pero no me sale el término general f(n). Si “es majo y se deja” quizá se saque algo de eso.
josejuan | 15 de February de 2010 | 09:47

Rober, eso ya lo hice en

http://gaussianos.com/los-numeros-de-catalan/#comment-33308

pero sigue saliendo una serie difícil de sumar.
Trackback | 15 Feb, 2010

Первый Карнавал Математики: Резюме статей | Blog na matematicheskom l'ubopytstve
Trackback | 15 Feb, 2010

Le premier Carnaval de Mathématiques : Un résumé d’articles | Blog sur des curiosités mathématiques
Trackback | 15 Feb, 2010

The first Carnival of Mathematics: Articles summary | Blog on mathematical curiosities
Trackback | 15 Feb, 2010

Erster Karneval der Mathematik: Zusammenfassung der Artikel | Blog auf mathematischen Neugieren
Rober | 15 de February de 2010 | 15:34

¡¡ ups !! eso me pasa por pensar antes de leer

De todas formas, la visualización de la distribución de los unos y los ceros en cada columna me recuerda a algo. Quizá algo relacionado con los árboles de búsqueda dicotómicos, no sé, algo por el estilo.

Pero a lo único que llego es que en cada columna decimal “c” (¿no debería decirse “binarial” o algo así?) los valores del sumando n>=c son cero. Para 1<n<c dependen de la paridad de la parte entera de (c-1)/n.

Es decir: la suma de unos de cada columna será la cantidad de números pares |(c-1)/n| desde 1 hasta c-1.

Pero no sé como formularlo. Y luego aún habría que sumar todas las columnas y ver si se puede simplificar.
mich | 11 de March de 2010 | 06:02

a ver si no estoy equivocado esto es una serie de fourier

A= \sum_{n=1}^{\infinity} {1 \over 2^n + 1}

y es una serie convergente con suma igual a:
A= {pi \over 2}*{pi e^(2*pi)+1 \over pi*e^(2*pi) – 1} – {1\over 2}

sorry no se escrivir con esto espero que os podais hacer a la idea de lo que digo
anarika | 12 de March de 2010 | 02:44

podrias poner la bibliografia completa porfavor? graciaas!