jueves, 19 de noviembre de 2026

Subconjuntos de algunas matrices triangulares (1)

En Matemática Discreta son muy frecuentes las matrices triangulares, generalmente referidas como T(n,k). La más popular de ellas es el triángulo de Pascal o aritmético. En él, el significado de las filas es uno y los de las columnas otros muy distintos.

Triángulo de Pascal

Es un ejemplo clásico de matriz triangular con propiedades interesantes. Como es un tema muy popular, nos limitamos aquí a señalar el papel de filas y columnas en ella. Basta estudiar la imagen:

 


En ella se observa que las filas suman una potencia de 2, y que las columnas van recorriendo los números poligonales y piramidales. Si sumamos adecuadamente para formar el triángulo de Bernouilli, aparecerían otras propiedades. Lo dejamos como ejemplo.

Números de Stirling de primera clase

Es otro ejemplo clásico de matriz triangular con significados en filas y columnas.

Al número de permutaciones de n elementos que están formadas por k ciclos le llamaremos número de Stirling de primera clase sin signo, y lo representaremos por S(n,k). Así, S(5,2)=50, ya que la descomposición básica en dos ciclos es

(1,2,3,4)(5), (1,2,3,5)(4), (1,2,4,5)(3), (1,3,4,5)(2), (2,3,4,5)(1),
(1,2,3)(4,5), (1,2,4)(3,5), (1,3,4)(2,5), (2,3,4)(1,5), (1,2,5)(3,4), (1,3,5)(2,4), (2,3,5)(1,4),
(1,4,5)(2,3), (2,4,5)(1,3), (1,3,5)(1,2)

Resultan en total 15 configuraciones, pero cada conjunto de cuatro elementos equivale a seis ciclos (permutaciones circulares, factorial de n-1=3). Así, (1,2,3,4) contiene en realidad los ciclos (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3)(1,4,3,2) y cada conjunto de tres equivale a dos ciclos (y los de dos, a uno solo), luego tendremos:

S(5,2)=5*6+10*2=50

Es evidente que S(n,n)=1, pues sólo la identidad contiene n ciclos, y que S(n,1)=(n-1)!, pues representaría a las permutaciones circulares. Además, S(n,0)=0, valor adoptado por definición. Piensa también por qué S(n,n-1)=Cn,2 (número combinatorio).

El resto de números de Stirling se obtiene mediante la fórmula de recurrencia

Si copiamos la matriz triangular de estos números, tendremos:

S(n+1,k)=S(n,k-1)+nS(n,k)

Ver https://hojaynumeros.blogspot.com/2013/10/ciclos3-numeros-de-stirling-de-primera.html

En la imagen observamos la matriz triangular de estos números:


La suma de las filas es el factorial del número de fila, porque es la unión de todas las posibilidades de descomposición en ciclos. Así:

0+24+50+35+10+1=120=5!

Por columnas, podemos recorrer todos los valores para un mismo caso de descomposición en ciclos. Por ejemplo, el número 3 admite tres descomposiciones en dos ciclos: (12)(3), (13)(2) y (23)(1)

Una columna especial es la de un ciclo, porque coincide con los factoriales de N-1. Las siguientes pueden obedecer a recurrencias, sumas o fórmulas, como la correspondiente a dos ciclos, que sigue la siguiente recurrencia:

a(n+1) = (n+1)*a(n) + n!.

Por ejemplo, para n=3: a(4)=4*11+3!=50.

Se pueden recorrer las distintas columnas y descubrir propiedades interesantes.

 Números eulerianos

Los números eulerianos (o de Euler), representados, por ejemplo, mediante A(n,k), equivalen al número de permutaciones sin repetición del número N en las que se producen k ascensos, es decir, pares de elementos consecutivos en los que el primero es menor que el segundo.

Por ejemplo, A(4,2)=11, porque según el listado elaborado con la hoja Cartesius, existen 11 permutaciones del conjunto (1,2,3,4) que presentan dos ascensos:


Si poseen dos ascensos, sus permutaciones simétricas poseerán uno, luego A(4,1)=11 también.

Si escribimos los números eulerianos en una matriz triangular, los elementos de cada fila serán simétricos, y su suma coincidirá con el factorial de N.

Puedes darte una idea con los datos de esta tabla (elaboración propia):


Los datos son simétricos y su suma por filas es el factorial de N.

Estos números son los coeficientes de los polinomios eulerianos, pero no seguiremos por ahí.

Para encontrar una función que nos devuelva un valor concreto de A(N,k) podemos usar esta relación de recurrencia:

A(N,k) = (k+1)A(N-1,k) + (n-k)A(n-1,k-1)

El primer sumando representa las permutaciones de N elementos que mantienen los mismos ascensos existentes en N-1. La idea es sencilla, ya que N es mayor que los elementos de las permutaciones de N-1, y para que no cambie el número de ascensos, o bien N es el primer elemento, o bien, se ha intercalado en un ascenso, con lo que se gana uno, pero se pierde otro.

Por ejemplo, si en el ascenso 2, 4 intercalamos un 5, quedará 2, 5, 4. Se gana el ascenso 2,5 pero se pierde el 2,4. Queda igual el número de ascensos, pero ha habido k+1 inclusiones. De ahí (k+1)A(N-1,k).

El otro sumando representa los ascensos que se crean nuevos, al intercalar N entre dos elementos que no presentaban ascenso, que son N-k en total. En ellos se crea un ascenso nuevo, por lo que es necesario que la permutación primitiva tenga un ascenso menos, es decir, (n-k)A(n-1,k-1).

Función EULERIANO

Esta recurrencia nos sirve para crear una función EULERIANO(N,K). Para no tener que manejar una matriz completa, se usan aquí dos vectores, a y b, que van tomando valores con N y N-1 a lo largo del desarrollo. Está escrita en VBasic por comodidad de creación de tablas en Excel, pero es fácilmente trasladable a otros lenguajes:

Function euleriano(n, k)

Dim a(50), b(50)’ Vectores para la recursión

Dim i, j, p

 

If n < 3 Or k = 0 Or k = n - 1 Then euleriano = 1: Exit Function

If k > n - 1 Then euleriano = 0: Exit Function ‘Casos particulares

For i = 0 To 50: a(i) = 0: b(i) = 0: Next I ‘Vaciado de vectores

b(0) = 1: b(1) = 1

For i = 3 To n ‘La recurrencia comienza con n=3

a(0) = 1: a(n - 1) = 1

For j = 1 To i - 1

a(j) = (j + 1) * b(j) + (i - j) * b(j - 1) ‘Recurrencia

Next j

For p = 1 To i: b(p) = a(p): Next p’ Cambio de papeles entre a() y b()

Next i

euleriano = a(k)

End Function

 

Con esta función se ha elaborado la tabla de más arriba.

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

Fórmula explícita

Se demuestra que un número euleriano se calcula mediante la fórmula


Se puede traducir a PARI. Por ejemplo, estas líneas reproducen los valores para N=8:

T(n, k) = sum( j=0, k, (-1)^j * (k+1-j)^n * binomial( n+1, j))

for(i=0,7,print1(T(8,i),", "))

 

 

Con esta fórmula se pueden construir las columnas de la matriz. Por ejemplo, la columna de k=1, 1, 4, 11, 26, … sigue la expresión 2m-(m+1), y la de k=2, sigue la expresión 3m - (m+1)*2m + (1/2)*m*(m+1)

 

Podemos generalizar a todas las columnas si usamos una suma y sustituimos k por un valor concreto. Por ejemplo, para k=4 obtendríamos:


T(n) = sum( j=0, 4, (-1)^j * (5-j)^n * binomial( n+1, j))

for(i=5,10,print1(T(i),", "))

 

El resultado concuerda con la matriz triangular obtenida:

 


Hemos obtenido el desarrollo por columnas.


Seguiremos viendo ejemplos en la siguiente entrada.

lunes, 9 de noviembre de 2026

Regreso 17 – Cuestiones sobre los k-casi primos

En el año 2009 presenté los números k-casi primos, que son aquellos que poseen k divisores primos, no necesariamente distintos, así, 48=24*3 es 5-casi primo, y 30=2*3*5, 3-casi primo.

https://hojaynumeros.blogspot.com/2009/12/primos-semiprimos-y-casi-primos-1.html

Casos particulares son los primos, para k=1, los semiprimos, con k=2 y un caso particular para k=3 son los esfénicos, que poseen tres factores primos distintos, como el 42=2*3*7

Es un concepto elemental, por lo que su presencia en Internet no es muy extensa. Una excepción interesante es la página https://mathworld.wolfram.com/AlmostPrime.html

En ella se reproducen fórmulas teóricas que cuentan el número de k-casi primos menores o iguales a un número dado N. Comenzaré con esa cuestión, pero desarrollándola con herramientas informáticas.

Distribución de los k-casi primos

Para identificar los números de este tipo podemos usar la función BIGOMEGA, que cuenta todos los factores primos con repetición. Algunos lenguajes de programación la tienen incorporada, como PARI. En él basta igualar esa función al valor de k:

escasiprimo(n,k)=bigomega(n)==k

Con eso basta.

Con este código encontramos todos los 5-casi primos del 1 al 500:

? escasiprimo(n,k)=bigomega(n)==k
for(a=1,500,if(escasiprimo(a,5), print1(a,", ")))

%3 = (n,k)->bigomega(n)==k

32, 48, 72, 80, 108, 112, 120, 162, 168, 176, 180, 200, 208, 243, 252, 264, 270, 272, 280, 300, 304, 312, 368, 378, 392, 396, 405, 408, 420, 440, 450, 456, 464, 468, 496, 500, …

Están publicados en https://oeis.org/A014614, y su tratamiento es elemental.

Para hojas de cálculo vale esta versión de la función BIGOMEGA:

Function bigomega(n)

Dim f, a, b

Dim vale As Boolean

  

a = n

f = 2: b = 0

While f * f <= a ‘f Es un posible factor primo

vale = False

While a / f = Int(a / f)’ ¿Es divisor?

b = b + 1’ Se cuentan repeticiones

a = a / f

vale = True

Wend

If f = 2 Then f = 3 Else f = f + 2 ‘Siguiente factor

Wend

If a > 1 Then b = b + 1’último factor

bigomega = b

End Function

Con esta función podemos construir ESCASIPRIMO(N,K):

Function escasiprimo(n, k) As Boolean

Dim a

a = bigomega(n)

If a = k Then escasiprimo = True Else escasiprimo = False

End Function

 
De esta forma, basta esta condición para encontrar k-casiprimos. En la imagen podemos observar las primeras soluciones para 5-casiprimos, ya estudiadas en PARI:




 
Cuestión 1: Estadísticas

¿Cuántos casi primos de cada clase son menores o iguales a un número n?

Para encontrar las frecuencias, bastará dimensionar un vector para ellas, por ejemplo, del 1 al 10, y dejar el 11 para “otros mayores de 10”

No es difícil la operación. La siguiente función las calcula y devuelve una lista con comas, para que se pueda convertir el texto en columnas.

Function estad_casi$(n)

Dim v(11)

Dim a, i, j

Dim s$

s$ = ""‘Contenedor de la lista de frecuencias

For i = 1 To 11: v(i) = 0: Next I ‘Frecuencias a cero

For j = 2 To n

a = bigomega(j) ‘Encuentra el tipo de casiprimo

If a > 10 And a > 0 Then v(11) = v(11) + 1 Else v(a) = v(a) + 1

‘Se cargan las frecuencias en el vector

Next j

For i = 1 To 11

s = s + ajusta(v(i)) ‘Se elabora la lista

If i < 11 Then s = s + ","

Next i

estad_casi = s

End Function

 

Por ejemplo, la estadística para n=5000 es la siguiente:

 

669,1365,1273,832,452,224,104,47,22,7,4

 

Si usamos la prestación de “Texto a columnas” podemos construir tablas de frecuencias y gráficos en hoja de cálculo:




Los resultados son lógicos. El máximo se presenta en los semiprimos. Los cuatro que poseen bigomega mayor que 10 son:


Sería interesante un ajuste a algún tipo de distribución, como la del modelo logístico de las epidemias. Ahí dejo el reto.

Cuestión 2: Descomposición de 2k-casiprimos en dos k-casiprimos

Un ejercicio sencillo es el de obtener la descomposición de un 2k-casiprimo en dos k-casiprimos. Nos permitirá desarrollar algunas técnicas.

Con una función

900=22*32*52 se puede descomponer en los 3-casiprimos 12=2*2*3 y 75=3*5*5. ¿En cuantos productos más? Con esta función se pueden encontrar todos. Como es tan solo una demostración, no se ha previsto que n no sea 2k-casiprimo, y se ha adaptado al ejemplo, suponiendo k=3. Para otro ejemplo, basta corregir.

Function dosfact$(n)

s = ""

For i = 2 To Sqr(n)

If n / i = n \ i Then’ Es divisor

If bigomega(i) = 3 Then’ Es 3-casiprimo

j = n / i: s = s + ajusta(i) + "×" + ajusta(j) + "  "

End If

End If

Next i

dosfact = s

End Function

 

Nos resultan cuatro descomposiciones:


12×75, 18×50, 20×45, 30×30 

Con Cartesius

Con esta herramienta también se puede intentar

(https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius)

Usamos las condiciones:

xtotal=3

xt=2,3,5

contar(2)<3

contar(3)<3

contar(5)<3

creciente


Piden combinar los tres números primos de 900 de forma que ninguno se repita más de dos veces. Así resultarán 3-casiprimos divisores de 90.

 

Sus desarrollos en factores resultan ser:


 

Y sus productos:


Obtenemos los mismos factores casiprimos. Al emparejarlos resultan los cuatro productos.

Razonamos

No son necesarias las herramientas informáticas en este caso. Si cada factor ha de poseer tres factores primos, sólo uno de ellos se podrá repetir, porque 900 no posee factores elevados a un exponente mayor que 2, luego tenemos: un factor sin repetición, 2*3*5 y seis factores con un elemento repetido. Como hay tres factores distintos en 900, y solo uno se repite, ese dará lugar a dos casos, y seis en total. Sumamos y nos resultarán siete factores posibles.

El principio de inclusión y exclusión nos ayuda a generalizar a más factores:

Card(AÈBÈC) =Card(A) + Card(B) + Card(C) - Card(AÇB) - Card(AÇC) - Card(BÇC) +  Card(AÇBÇC)

En este caso, podemos encontrar el número máximo combinaciones con repetición de los factores de 900 y restarle los arreglos no permitidos porque supongan repeticiones de tres o cuatro veces:

Sería:

Se deja así para quienes quieran seguir razonando.

Para casos más complejos podemos acudir a unas entradas recientes de este blog, que tratan el tema de los submulticonjuntos.

Cuestión 3: Además de casiprimos, ¿de qué otro tipo son?

Triangulares

Si pensamos en k-casiprimos triangulares, la primera idea es acudir a los semiprimos. Si N=n(n+1)/2 por ser triangular, uno de los factores de N deberá ser par, sea por ejemplo, n, y en ese caso n/2 y n+1 deberán ser primos. Si el factor par es n+1, lo serán (n+1)/2 y n. En ambos casos, el semiprimo deberá ser producto de un primo p en el que p+1 o p-1 sea doble de un primo. Los primeros ejemplos son: 6=3*4/2=3*2, 10=4*5/2=2*5, 15=5*6/2=5*3, …Todos ellos son triangulares y también semiprimos.

Con estas líneas los identificamos en PARI

a(n)=bigomega(n)==3&&omega==3&&(8*n+1)
for(k=4,5000,if(a(k)>0,print1(k,", ")))

La expresión 8*n+1 viene de que es cuadrada en los triangulares.

6, 10, 15, 21, 55, 91, 253, 703, 1081, 1711, 1891, 2701, 3403, …

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

Para los demás k-casiprimos, basta igualar bigomega a k en el anterior código PARI. Por ejemplo, los primeros triangulares 5-casiprimos son:

120, 300, 378, 496, 630, 780, 990, 1128, 1485, 1540, 1596, 2556, 2628, 2850, 3160, 3321, 3570, 3828, 4095, 4851, …

Están publicados muchos casos.

Oblongos

Los oblongos poseen la fórmula N=k(k+1), luego salvo 6=2*3, no podrán ser semiprimos. Los primeros 3-casiprimos lo serán si son doble de los triangulares semiprimos estudiados en el apartado anterior:

12, 20, 30, 42, 110, 182, 506, 1406, 2162, 3422, 3782, …

Han de tener un factor primo igual a 2, y de ahí que resulten muchos dobles de los anteriores. Pueden ser múltiplos de 4,  y así obtenemos el 12 y el 20 de nuevo. No hay más posibilidades.

Si buscamos ejemplos con k mayor que 3, se multiplican las soluciones, como 56=7*8 con k=4, 72=8*9 con k=5, y así con valores mayores. Su abundancia les quita interés.

Cuadrados o cubos

Dependerá del valor de k. Es fácil razonar que si es múltiplo de 2, podrán aparecer cuadrados, como 4=2*2, semiprimo, 36=2*2*3*3, con k=4, y cubos, con k múltiplo de 3. No tienen más misterio.

Números de Fibonacci

En este blog se ha usado la función esfibo:

Function esfibo(n) As Boolean 'devuelve verdadero si N es de Fibonacci
Dim f As Boolean
Dim a

f = False
a = 5 * n * n + 4
If escuad(a) Then f = True
a = 5 * n * n - 4
If  f = True
esfibo = f
End Function

Con ella y bigomega se pueden encontrar. Si los traducimos a PARI se obtienen los primeros:

Para semiprimos usamos

a(n)=bigomega(n)==3&&(issquare(5*n*n+4) || issquare(5*n*n-4))
for(k=4,5000,if(a(k)>0,print1(k,", ")))

Resultan estos primeros ejemplos:

21, 34, 55, 377, 4181, 17711, 121393, …

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

Con k=3 sólo han sido publicados los casos de esfénicos, más general es

8, 610, 987, 10946, 75025, …

Es un camino a seguir para buscar más casos.

 

 

 

viernes, 30 de octubre de 2026

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.