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.

No hay comentarios: