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.

TriánguloTomemos 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 trivalentePor 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.

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.

25 Comentarios

  1. 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.

    Publica una respuesta
  2. 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!)

    Publica una respuesta
  3. 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?

    Publica una respuesta
  4. 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.

    Publica una respuesta
  5. 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….!

    Publica una respuesta
  6. 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!

    Publica una respuesta
  7. ¡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…

    Publica una respuesta
  8. 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…

    Publica una respuesta
  9. 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!

    Publica una respuesta
  10. 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

    Publica una respuesta
  11. 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)

    Publica una respuesta
  12. 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)}

    Publica una respuesta
  13. 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).

    Publica una respuesta
  14. uff la función q-Digamma me queda muy muy lejos!intentare buscar algo a ver..

    Publica una respuesta
  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.

    Publica una respuesta
  16. ¡¡ 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.

    Publica una respuesta
  17. 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

    Publica una respuesta
  18. Hola, me gustaría que saber, o dónde poder consultar, como se obtienen esas expresiones de C_n y esas relaciones de recurrencia.

    Partiendo del problema de las parejas de paréntesis, yo he llegado a la relación de recurrencia:
    C_n = 2C_{n-1} + 2C_{n-2} - C_{n-3}

    Supongo que también influye el planteamiento del problema que uno elija, ya que hay varias formas equivalentes de presentarlo…
    Espero que me podáis echar una manita. 🙂
    De momento probaré desde algún otro planteamiento a ver qué sale.

    Publica una respuesta
  19. También he sacado:
    C_n = C_{n-1} + C_{n-2} +2 \sum_{i=1}^{n-2} C_i

    No consigo obtener relaciones como las que aparecen aquí o en la Wikipedia 🙁

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Este artículo es mi aportación a la primera edición de Carnaval de Matemáticas organizado…
  2. Los números de Catalan - [...] Los números de Catalan gaussianos.com/los-numeros-de-catalan/  por Phoenix-ALX el 16:28 UTC [...]
  3. Первый Карнавал Математики: Резюме статей | Blog na matematicheskom l'ubopytstve - [...] версией в каталанском языке), в Gaussianos они говорят нам о числах Каталанского языка, но нет, он не имеет ничего…
  4. Le premier Carnaval de Mathématiques : Un résumé d’articles | Blog sur des curiosités mathématiques - [...] et des produits infinis (avec sa version originale en catalan), dans Gaussianos ils nous parlent des nombres du Catalan,…
  5. The first Carnival of Mathematics: Articles summary | Blog on mathematical curiosities - [...] and infinite products (with his original version in Catalan), in Gaussianos they speak to us about the numbers of…
  6. Erster Karneval der Mathematik: Zusammenfassung der Artikel | Blog auf mathematischen Neugieren - [...] zu beschreiben, (mit seiner originalen Version sprechen sie in Katalanisch), in Gaussianos uns von den Nummern des Katalanisches, aber…

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 *