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.
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:
Publicar un comentario