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.

 

Números poligonales generalizados

Algunos conceptos matemáticos, que se basaron inicialmente en los números naturales, fueron después adaptados a otros tipos de números. Esto ocurrió con los números poligonales, que, al superar su carácter inicial geométrico, se generalizaron a los números enteros, pues ya no era necesario que su orden fuera positivo, al no representar una longitud. Esta decisión les abrió a nuevas posibilidades, por lo que han perdurado.

Todo número poligonal viene dado por esta fórmula muy popular:

Si permitimos que n sea cero o negativo, obtendremos los llamados números poligonales generalizados.

Si n es positivo, resultará un número poligonal clásico, que siempre será entero, ya que en el numerador se restan dos números de la misma paridad. Si generalizamos a un número negativo, sea n=-m, al sustituir en la fórmula obtendremos

Esta expresión da lugar a una nueva clase de poligonales a los que llamaremos segundos poligonales del mismo orden. Con el añadido del cero, los números poligonales generalizados serán la unión de los clásicos con estos otros de segunda naturaleza.

Si imaginamos m=n, ocurrirá que PS_n=P_n+(k-4)n

Comparemos, por ejemplo, las dos clases de hexagonales:

Los clásicos: 0, 1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231, de fórmula n(2n-1)

https://oeis.org/A000384

Los segundos: 0, 3, 10, 21, 36, 55, 78, 105, 136, 171, 210, de fórmula n(2n+1)

https://oeis.org/A014105

la diferencia entre sus elementos del mismo orden (k-4)n=2n

Así, 3-1=2*1, 10-6=2*2, 21-15=2*3, …

Lo interesante es que ambos conjuntos se pueden unir intercalando sus elementos. Para ello, habrá que demostrar que PS_n<P_n+1

Planteamos la diferencia:

Al ser el resultado positivo, podemos afirmar que P_n  < PS_n< P_n+1, y que, por tanto, se pueden intercalar ambas sucesiones con el título de números poligonales generalizados.

En el caso del hexágono formarían, intercalados, los números hexagonales generalizados:

0, 1, 3, 6, 10,15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136,153,

Nos llevamos la sorpresa de que son los números triangulares clásicos. Ya volveremos sobre ellos.

Casos particulares

Los triangulares se convierten en otros triangulares al cambiar de índice positivo a negativo, y los cuadrados permanecen iguales. Los casos interesantes comienzan con los pentagonales. Veremos los de este tipo y algunos más:

Números pentagonales generalizados

Los pentagonales clásicos, 1, 5, 12, 22, 35, 51, … siguen la fórmula

Es el caso particular de la fórmula general para k=5

Están publicados en https://oeis.org/A000326 y estudiados en mi publicación “Números poligonales” https://www.hojamat.es/publicaciones/poligonales.pdf

Según lo tratado anteriormente, los segundos pentagonales tendrán como fórmula

Son estos:

0, 2, 7, 15, 26, 40, 57, 77, 100, 126, 155, 187, …

Su diferencia con los clásicos del mismo orden es n: 2-1=1, 7-5=2, 15-12=3, …

Están publicados en https://oeis.org/A005449

La unión de las dos sucesiones formará esta otra, la de pentagonales generalizados:

0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117, 126, 145, 155, 176, 187, 210, 222, 247, 260, … (https://oeis.org/A001318)

Segundos pentagonales

Estudiamos algunos detalles de los segundos pentagonales:

Interpretación combinatoria

En la página de OEIS correspondiente se afirma que representan las cartas necesarias para construir un castillo de naipes. La clave está en el hecho de que PS(n+1)=PS(n)+2n+3:

Para el primer castillo se necesitan 3 cartas, y dado un castillo ya formado, deberemos añadir tres cartas por nivel (dos inclinadas y una horizontal) más la culminación, que serán dos cartas. En la imagen se entiende bien:

Las cartas de perfil azul corresponden a PS(3)=15 y las rojas 3*3+2=11, y al sumar obtenemos PS(4)=26

Recurrencias

Además de la ya tratada de 3n+2, existen varias publicadas en OEIS, pero no la que califico de “muy útil” (https://hojaynumeros.blogspot.com/2026/05/unas-recurrencias-muy-utiles.html) también nos vale, y no recurre al valor de n:

x_n= 3x_n-1-3x_n-2+x_n-3

En la entrada enlazada se explica su fundamento. Aquí basta con una comprobación en forma de tabla:

Números pentagonales generalizados

Al ser la unión de dos sucesiones, podemos unificar sus fórmulas mediante una función. En ella la variable m es útil para alternar los signos más y menos en el numerador.

pg(n)=my(m=truncate((n+1)/2));(3*m^2+(-1)^n*m)/2

for(k=1,20,print1(pg(k),", "))

Resulta:

1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117, 126, 145, 155, …

Era lo que se pretendía.

En su página de OEIS se incluyen muchas alternativas como fórmulas para esta sucesión.

 

Nuestra recurrencia “útil”

 

Al ser ambas sucesiones componentes generadas por la misma fórmula de recurrencia, bastará definir como elementos iniciales 0, 0, 1, 2, 5, 7 y aplicar

x_n= 3x_n-2-3x_n-4+x_n-6

Así: 3*5-3*1+0=12, 3*7-3*2+0=15, 3*12-3*5+1=22, …

Propiedad de Conway

La tercera parte de un triangular es un pentagonal generalizado si no es del tipo 3n+1

En esta tabla figuran los primeros triangulares y su tercera parte si es válida la para la propiedad:

0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 ...

0    1 2        5  7       12 15      22 26       35  40          51 ...

T(3n)/3=3n*(3n+1)/6=(9n²+3n)/6=(3n²+n)/2

T(3n-1)/3=(3n-1)(3n)/6=(3n²-n)/2

En ambos casos resulta un pentagonal generalizado.

 Otra propiedad: 24*a(n)+1 es un cuadrado

24(3n²+2)/2+1=36n²+24n+1=(6n+1)²

E igual con los pentagonales clásicos

Números heptagonales generalizados

Siguiendo los mismos razonamientos que con los pentagonales, esta otra sucesión será la unión de los heptagonales clásicos, de fórmula HP(n)=n(5n-3)/2 y los “segundos”, provenientes de órdenes negativos HPS(n)=n(5n+3)/2.

La sucesión resultante es, en sus primeros términos:

0, 1, 4, 7, 13, 18, 27, 34, 46, 55, 70, 81, 99, 112, 133, 148, 172, 189, 216, 235, 265, 286, 319, 342, 378, 403, 442, 469, 511, 540, 585, …

Está publicada en https://oeis.org/A085787, y los segundos heptagonales en https://oeis.org/A147875

Propiedades

A continuación, se verán algunas propiedades de ambas sucesiones:

Los segundos heptagonales son suma de una progresión geométrica, la b(n)=5*n+4, con primer término b(0)=4. En efecto, la suma será S(n)=(4+5*(n-1)+4)*n/2=n(5n-3)/2

Como todos los números de estos tipos siguen la recurrencia

x_n= 3x_n-1-3x_n-2+x_n-3

27=3*13-3*4+0, 46=3*27-3*13+4, …

Esta recurrencia se extiende a toda la sucesión generalizada de igual forma que en el caso de pentagonales.

De forma similar a los pentagonales, se cumple que 40a(n)+9 es un cuadrado:

40*n*(5n±3)/2+9=100n²±60n+9=(10n±3)²

Regresos 16 (3): Particiones condicionadas con PARI

En la anterior entrada se desarrolló un ejemplo de particiones condicionadas con Cartesius y un Buscador. Consistía en descomponer el número 50 en sumandos cuadrados, sin importar el número de ellos que usemos, pero que no pasara de 3. Las soluciones resultaron ser 50=25+16+9=25+25=49+1

Ahora repetiremos el ejemplo con las herramientas del lenguaje PARI.

En PARI se cuenta con la función FORPART, que recorre una partición cualquiera, en la que se pueden integrar condicionantes. Para el ejemplo actual valdría este código:

a(n) = {nb = 0; forpart(p=n, if (#p && (#select(x->issquare(x), Vec(p)) == #p), nb+=1;print(p)), , 3);nb; }
print(a(50))

Cuesta entender todo lo escrito, pero consiste en iniciar un contador nb, recorrer todas las particiones con forpart y condicionarlas con x->issquare(x). El 3 que aparece es el tope para el número de elementos de la partición. Finaliza incrementando el contador e imprimiendo resultados. Así queda en la página oficial de PARI:

 

Coincide con las anteriores herramientas

Segundo ejemplo

Encontrar el número de particiones de un número en números primos sin otro condicionamiento. Por ejemplo, con el número 20:

Utilizamos el código PARI siguiente:

a(n) = {nb = 0; forpart(p=n, if (#p && (#select(x->isprime(x), Vec(p)) == #p), nb+=1), , ); nb; }
print(a(20))

Lo probamos y resulta que son 26:

Si deseamos ver las 26 particiones, le añadimos un print(p) detrás de nb+=1. Observa la imagen:

Con el Buscador se puede comprobar. Basta corregir las líneas de filtro, usando ESPRIMO en lugar de ESCUAD. Se omiten los detalles, ya explicados en la anterior entrada.

Se ha usado como tope el 10, que es máximo número posible de sumandos primos.

Nos puede interesar aplicar otra condición. En el ejemplo anterior se podría exigir que los primos fueran pitagóricos, del tipo 4k+1. Resultaría:

Se ha añadido la condición x%4==1 (el signo % significa MÓDULO)

 Condiciones más exigentes

Partición con sumandos coprimos

He encontrado este ejemplo en https://oeis.org/A000837, y lo uso para resaltar la economía de medios del lenguaje PARI. He adaptado el código a este documento:

s=0;forpart(X=20, s+=(gcd(X)==1);print(s))

Con esta simple línea encontramos que existen 582 particiones en las que el conjunto de sumandos posee MCD igual a 1 (no se afirma que sean primos dos a dos). Aquí, la condición fundamental es gcd(X)==1

Función Q(n)

Se denomina así al número de particiones de un número en elementos distintos. Recordamos aquí que estas particiones son sencillas de encontrar con Cartesius. Basta usar la condición NO REPITE.

Estas son las condiciones para las particiones del número 10 en sumandos distintos:

xrango=10

xt=1..10

no repite

suma=10

creciente

Su solución es

Son diez en total, pero el proceso resulta lento e inestable.

En OEIS (https://oeis.org/A000009) se incluye este código PARI:

{a(n) = my(c); forpart(p=n, if( n<1 || p[1]<2, c++; for(i=1, #p-1, if( p[i+1] > p[i]+1, c--; break)))); c}; /* Michael Somos, Aug 13 2017 */

Es algo oscuro a la hora de entenderlo, pero funciona:

En el elemento correspondiente al 10 observamos que Q(10)=10, tal como resultó en Cartesius.

Con el Buscador

Anulamos los filtros o restricciones, pero en el momento de llegar a la suma de la partición añadimos esta condición:

vale = True

If pp > 1 Then

For j = 2 To pp

For k = 1 To j - 1

If su(e(j)) = su(e(k)) Then vale = False

Next k

Next j

End If

 

If vale Then

De esa forma, sólo nos devolverá las particiones con elementos distintos:

Según un importante teorema ya visto en este blog, el número de estas particiones coincide con las conseguidas si se restringen los sumandos a ser impares.

En el ejemplo del 10 nos resultarían, como era de esperar, 10 particiones con este código:

a(n) = {nb = 0; forpart(p=n, if (#p && (#select(x->x%2==1, Vec(p)) == #p), nb+=1;print(p)), , 3);nb; }
print(a(10))

Con Cartesius bastarían las condiciones

xrango=10

xt=1..10

xt=filtro(impar)

suma=10

creciente

No es recomendable por su lentitud.

Sin más explicaciones, este sería el resultado si eliminamos los sumandos pares:

 

Particiones con un número par o impar de sumandos

En estos ejemplos usaré PARI:

Con un número par:

Es importante la parte #p%2==0,nb+=1, pues % es la operación MODULO y nos indica que la partición tiene un número par de elementos #p.

a(n) = {nb = 0; forpart(p=n, if(#p%2==0,nb+=1), , ); nb; }
print(a(20))

Nos resulta que existen 317 particiones con un número par de elementos. Si deseamos datos de los primeros números obtendremos:

Coinciden con los publicados en https://oeis.org/A027187

Particiones con número impar de elementos:

Bastaría cambiar #p%2==0 por #p%2==1:

Publicados en https://oeis.org/A027193

Podemos usar ambas situaciones en funciones separadas, y experimentar algo con ellas. Por ejemplo, que las de número par sean dos más que las de impar:

a(n) = {nb = 0; forpart(p=n, if(#p%2==0,nb+=1), , ); nb; }

b(n) = {nb = 0; forpart(p=n, if(#p%2==1,nb+=1), , ); nb; }

for(i=1,100, if(a(i)==b(i)+2,print1(i,”, “)))

No tiene mucho interés, porque en los primeros números solo se cumple en el 8 y el 10.

También se pueden contar por separado las particiones de cardinal par y las de impar en la misma función. La siguiente busca si el número de particiones de orden par es dos unidades mayor que las de impar en un mismo número n.

c(n) = {my(nb = 0,na=0);forpart(p=n, if(#p%2==0,nb+=1,na+=1,), , ); nb==na+2 }
for(i=1,30, if(c(i)==1,print1(i,”, “)))

Escasean también los resultados.

Lo dejamos aquí. Ya se ha abierto una puerta a más experimentaciones.

Unos detalles para finalizar

PARI posee la función numbpart, que cuenta el número de elementos de una partición. Este código elabora un listado de los números con un número par de particiones distintas:

a(n)={my(c);c=numbpart(n);if(c%2==0,return(c))}
for(i=1,50,if(a(i)>0,print1(i,", ")))

Particiones con producto acotado

En la primera parte de la instrucción forpart se puede incluir toda una línea de código. Esto permite calcular productos en las particiones y condicionarlos.

Por ejemplo, lo siguiente encuentra aquellas particiones de n=5 cuyo producto es mayor que 3. Es importante destacar la forma en la que hay que usar las distintas partes de una partición con Vec(p)[k]):

a(n) = { nn=0; forpart(p=n, pp=1;for(k=1,#p,pp=pp*Vec(p)[k]);if(pp>3,nn+=1;print(p);p));nn }
print(a(5))

Resultado:

Otro ejemplo: podemos reproducir el contenido de https://oeis.org/A319005

Number of integer partitions of n whose product of parts is >= n.

 1, 1, 1, 1, 2, 2, 5, 7, 13, 18, 28, 40, 60, 80, 113, 152, 205, 266, 353, 454, 590, 751, 959, 1210, 1529, 1905, 2381, 2953, 3658, 4501, …

Usaremos

a(n) = {nn=0; forpart(p=n, pp=1;for(k=1,#p,pp=pp*Vec(p)[k]);if(pp>=n,nn+=1));nn }
for(i=1,30,print1(a(i),", "))

Resultado:

Con estos ejemplos se reconoce la enorme capacidad de PARI para manejar particiones. Paramos ejemplos por ahora.