lunes, 16 de febrero de 2015

Números “Tribonacci”


Los números “tribonacci” son análogos a los de Fibonacci, pero generados mediante recurrencias de tercer orden homogéneas.  Existen muchas sucesiones con este nombre, según sean sus condiciones iniciales. Aquí comenzaremos con la contenida en

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

pero podemos cambiar más tarde si surgen propiedades interesantes para su estudio con hoja de cálculo.

En estos números la fórmula de recurrencia posee todos sus coeficientes iguales a la unidad

xn= A*xn-1+B*xn-2+C*xn-3 se convertiría en

xn= xn-1+xn-2+xn-3

Al igual que en el caso de Fibonacci, los dos valores iniciales también valen 1, y el tercero, 2, pero ya hemos explicado que existen otras variantes. Dejamos los enlaces de algunas de ellas:

http://oeis.org/A000073  comienza con a(0)=a(1)=0, a(2)=1
http://oeis.org/A000213  con a(0)=a(1)=a(2)=1
http://oeis.org/A001590 con a(0)=0, a(1)=1, a(2)=0
http://oeis.org/A081172 comienza con 1,1,0.

Y hay más.

Como ya hemos indicado, nosotros comenzaremos con:

Condiciones iniciales: x0=1, x1=1x2=2 Ecuación de recurrencia: xn= xn-1+xn-2+xn-3

Los primeros términos son:

 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744,… http://oeis.org/A000073

Como en otras entradas sobre el mismo tema, podemos acudir a nuestra herramienta de hoja de cálculo para sucesiones recurrentes

http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2

En la imagen puedes identificar los coeficientes y valores iniciales



Con el botón “Ver sucesión” podremos obtener el listado de estos números:


Ecuación característica

Al igual que en otras sucesiones recurrentes, su ecuación característica se formará a partir de sus coeficientes, en este caso todos iguales a 1, luego será x3-x2-x-1=0

Con nuestra herramienta podemos encontrar sus raíces:



La misma solución obtenemos con WxMaxima



Recordemos que los elementos de las sucesiones recurrentes se pueden expresar como suma de potencias de las tres soluciones, pero con estos números ocurre como con algunos similares (los de Fibonacci, Perrin o Narayana), y es que las raíces complejas, al tener módulo inferior a la unidad, tienden a cero si prolongamos la sucesión. Por ello, las potencias de la raíz real, 1,839286…generan con bastante aproximación los números Tribonacci, y, lo que es lo mismo, esta constante coincidirá aproximadamente con el cociente entre dos de estos números consecutivos. Lo vemos con hoja de cálculo:



Por ello, al número 1,839286…se le llama Constante Tribonacci.

Función generatriz

Todas las variantes de las sucesiones Tribonacci comparten los mismos coeficientes de recurrencia, y por tanto también el denominador de su función generatriz. La que estamos estudiando en esta entrada, de inicio 1, 1, 2, se genera con la siguiente:


Al igual que con otras sucesiones, la comprobaremos con PARI:

write("sucesion.txt",taylor((x)/(1-x-x^2-x^3),x,20))

Te escribirá en un archivo sucesión.txt su desarrollo (este archivo lo deberás tener vacío en la misma carpeta que PARI), y aparecerán como coeficientes los términos de la sucesión Tribonacci:

x + x^2 + 2*x^3 + 4*x^4 + 7*x^5 + 13*x^6 + 24*x^7 + 44*x^8 + 81*x^9 + 149*x^10 + 274*x^11 + 504*x^12 + 927*x^13 + 1705*x^14 + 3136*x^15 + 5768*x^16 + 10609*x^17 + 19513*x^18 + 35890*x^19 + O(x^20)

Una excursión por la hoja de cálculo

Podemos usar la versión matricial de la generación de estos números para recordar algunos detalles sobre hojas de cálculo.

Es elemental comprobar que las ternas de números consecutivos de Tribonacci. T(n), T(n+1), T(n+2) pueden engendrar matricialmente la terna siguiente T(n+1), T(n+2), T(n+3), mediante la siguiente fórmula matricial:


Esta fórmula es adecuada para repasar las fórmulas matriciales de las hojas de cálculo. Comenzamos construyendo un esquema como el de la imagen:



Para efectuar el producto matrical deberemos usar la función MMULTI, con parámetros la primera matriz y la columna de la primera terna:

{=MMULT(D4:F6;H4:H6)}

Observa que como multiplicamos rangos de celdas, usamos el separador :

Para que la hoja entienda que se trata de una multiplicación matricial, cuando termines de escribir la fórmula, en lugar de terminar con INTRO, usaremos Ctrl+Mayúscula+INTRO. La aparición de las llaves es la señal de que la fórmula ha sido introducida correctamente.

Una vez efectuado el cálculo sobre una terna, basta que copies el resultado como dato, usando Copiar y Pegado especial como valores, y proseguirán apareciendo ternas nuevas.

Uno de los autovalores de la matriz que hemos usado es la constante de Tribonacci, 1,839286…La razón es que el polinomio característico de la matriz es el mismo que el de la ecuación característica de la recurrencia, x3-x2-x-1=0.

Curiosidades

En esta serie sobre sucesiones recurrentes solemos presentar en cada una de ellas propiedades curiosas, no todas las conocidas, que llenarían libros, sino las que más nos llamen la atención o se adapten mejor a las herramientas que usamos. Para la de Tribonacci presentaremos una propiedad combinatoria.

Particiones de un número en sumandos no mayores que 3

Los números de Tribonacci (salvo los iniciales) cumplen que T(N) coincide con las particiones de N-1 en sumandos que se pueden repetir, en cualquier orden y con los sumandos menores o iguales a 3. Por ejemplo, T(5)=7, que coincide con las particiones del número 4 en partes no superiores a 3:
Lo comprobamos con el listado obtenido con nuestra hoja no publicada “Cartesius”:



Observamos que resultan 7 particiones distintas.

Para T(4)=4 obtenemos el mismo resultado con particiones del número 3:


La razón de que esto funcione así es que cualquier partición de este tipo con N elementos ha resultado a adjuntar un 1 a las particiones de N-1, un 2 a las de N-2 y un 3 a las de N-3, con los que se cumple xn= xn-1+xn-2+xn-3 . Para que lo entiendas mejor hemos coloreado estos tres sumandos para el caso de T(6)=13: