La hoja de cálculo y los números de Catalan

Últimamente estoy volviendo a la Combinatoria, que tenía algo abandonada. Hoy es el turno de dar un repaso a los números de Catalan (Obtienen su nombre del matemático Eugène Charles Catalan):

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, …

(http://oeis.org/A000108)

Estos números se suelen introducir mediante las triangulaciones de polígonos, según puedes comprobar con esta imagen tomada de la Wolfram MathWorld:

 

(Fuente: http://mathworld.wolfram.com/CatalanNumber.html)

A la vista de la figura, y de la definición, se comprende que un triángulo solo se puede triangular de una forma, con lo que C(1)=1. Un cuadrilátero, según vemos, en dos, que son las diagonales, por lo que C(2)=2.

El pentágono se triangula según sus cinco vértices, lo que hace que C(3)=5. También puedes comprobar que C(4)=14 para el hexágono.

Así podríamos seguir.

Estos números son muy conocidos, y aquí sería inútil añadir más teoría. Por eso, nos dedicaremos solo al uso de la hoja de cálculo para calcularlos.

Para conocer mejor estos números puedes consultar:

https://www.youtube.com/watch?v=kjn9hFQK9aQ

(vídeo de Eduardo Sáenz de Cabezón)

https://es.wikipedia.org/wiki/N%C3%BAmeros_de_Catalan

https://www.gaussianos.com/los-numeros-de-catalan/

http://mathworld.wolfram.com/CatalanNumber.html

https://brilliant.org/wiki/catalan-numbers/

http://mathforum.org/advanced/robertd/catalan.html

En ellas y otras similares puedes encontrar propiedades y demostraciones. Como no es cuestión de repetir lo que en otras fuentes se explica mejor, daremos por supuestas las propiedades en lo que sigue y nos dedicaremos a plantear cálculos y cuestiones con Excel solamente, pues el programa Calc de LibreOffice también los lee, incluidas las macros más populares:

Fórmula directa

En esas páginas enlazadas figura la fórmula directa para calcular el enésimo número de Catalan.

En las hojas de cálculo dispones de la función COMBINAT para los números combinatorios C(m,n), FACT para el factorial n! y FACT.DOBLE para el doble factorial n!!

Con ellas podemos comprobar las tres fórmulas directas anteriores. Quedarían así:

=COMBINAT(2*N;N)/(N+1)

=FACT(2*N)/FACT(N+1)/FACT(N)

=2^N*FACT.DOBLE(2*N-1)/FACT(N+1)

Lo comprobamos con tres columnas paralelas en una tabla:

Aprenderás bastante del manejo de las hojas de cálculo con la construcción de esta tabla. Con ella comprobamos la equivalencia de las tres fórmulas. Si sabes añadir funciones a Excel, puedes definir una función con una de estas tres fórmulas. Elegimos la segunda, que solo usa la función FACT. Te sorprenderá su extensión, pero es que contiene tres llamadas a las funciones de Excel:

Function catalan(n)

catalan = Application.WorksheetFunction.Fact(2 * n) / Application.WorksheetFunction.Fact(n) / Application.WorksheetFunction.Fact(n + 1)
End Function

En la entrada de este blog enlazada a continuación puedes recordar el procedimiento para disponer de esta función en el Excel de tu ordenador:

https://hojaynumeros.blogspot.com/2013/09/tus-funciones-disponibles-en-todas-las.html

Así, si escribes =CATALAN(8) te devolverá 1430. Igualmente, puedes escribir operaciones con números de Catalan, como, por ejemplo, la diferencia entre dos consecutivos:

CATALAN(20)-CATALAN(19)=4796857230

Si deseas practicar un poco más con la hoja de cálculo, puedes comprobar o construir la función CATALAN con esta otra expresión:

 

Por ejemplo, 132=COMBINAT(12;6)-COMBINAT(12;5)

Otras expresiones de los números de Catalan

Mediante un producto:

Desde el segundo número de Catalan, siguiendo las propiedades contenidas en http://oeis.org/A000108:

a(n) = Product_{k=2..n} (1 + n/k), if n > 1.

Es fácil traducir este producto al Basic de Excel y Calc:

Function catalan2(n)

Dim k, p

 

p = 1

For k = 2 To n

p = p * (1 + n / k)

Next k

catalan2 = p

End Function

 

En esta captura de pantalla se refleja la comprobación del idéntico resultado para el número 8 en las dos versiones propuestas:

 

Mediante recurrencia

No es difícil demostrar, con cualquiera de las tres fórmulas directas, esta versión recursiva:

Podemos aprovechar las prestaciones de Excel en el uso de funciones recursivas. No es muy potente, pero para números sencillos funciona bien. Consiste en que una función se llama a sí misma.

Tienes una introducción a esta técnica en nuestro documento “Funciones y Macros”, descargable desde

http://www.hojamat.es/guias/descubrir/htm/macros.pdf

Para el caso de los números de Catalan proponemos este código:

 

Function catalan3(n)

Dim c

 

If n = 1 Then c = 1 Else c = catalan3(n - 1) * 2 * (2 * n - 1) / (n + 1)

‘Si n=1 declaramos que c=1 y, en caso contrario, catalan3 se llama sí misma en el valor n-1

catalan3 = c

End Function

 

Es un código muy compacto, pero que puede fallar para números grandes

He incorporado esta otra función en una hoja de cálculo descargable que contiene el material que se va desarrollando en esta serie de entradas

 

http://www.hojamat.es/blog/catalan.xslm

Otra forma de conseguir la recurrencia es mediante dos columnas, una con los índices y otra en la que cada número de Catalan depende del anterior:

Si n=1, a=1
A(n)=a(n-1)*2*(2*n-1)/(n+1)

Dejamos aquí los cálculos sobre los números de Catalan. Nuestro enfoque ha sido operativo, porque es un tema tan extenso y tan bien tratado en otras publicaciones que con una sola herramienta como la hoja de cálculo era algo inútil reproducir conceptos y cálculos.