jueves, 8 de enero de 2015

Sucesión de las vacas de Narayana


Proseguimos nuestro estudio de sucesiones recurrentes de tercer orden con la ideada por el hindú Narayana (siglo XIV), con la que intentaba calcular generaciones de vacas, al igual que Fibonacci lo hacía con conejos. Planteó lo siguiente:

Una vaca tiene anualmente una cría. Cada una de ellas, cuando ya es novilla a los cuatro años, también tiene una cría anual ¿Cuántas vacas habrá a los 20 años?

En libros y webs de Historia de las Matemáticas puedes encontrar cómo lo resolvió a partir de sumas de números consecutivos, pero a nosotros nos interesa en este momento su carácter de sucesión recurrente.

En efecto, supongamos que nace la vaca en el año 1. Se pasará tres años sin parir, por lo que la sucesión deberá comenzar con 1, 1, 1,… Al cuarto año tiene una cría, luego ya serán 2 vacas, y, como pare cada año, los siguientes números serán 3 y 4. Cuando la cría tiene 4 años, tendrá otra a su vez, y serán 6. En general, en cada generación habrá tantas vacas como las que haya actuales, más todas aquellas que ya tengan cuatro años, lo que nos lleva a que

xn=xn-1+xn-3

Según esto, la sucesión de Narayana es recurrente de tercer orden, y entra dentro del ciclo que estamos desarrollando.

Para entender mejor cómo organizaremos el estudio, puedes leer la entrada

http://hojaynumeros.blogspot.com.es/2014/11/sucesion-de-perrin.html

La definición de la sucesión, como todas las de su clase, se basa en dar la fórmula de recurrencia y las condiciones iniciales. Según lo explicado más arriba, son estas:

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

Acudiendo a la herramienta que usamos en esta serie (http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2) tendremos:

Planteamiento:










Resultado




Coincide con la sucesión publicada en http://oeis.org/A000930

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745,…

Ecuación característica

La ecuación característica correspondiente será X3-x2-1=0. Con el botón Resolver de esa hoja obtienes las tres soluciones de la ecuación, una real y dos complejas




Con wxMaxima:



Esta situación la hemos visto en sucesiones anteriores, y es que X(n) debe coincidir con la suma de las tres raíces elevadas a n, pero como el módulo de las complejas es menor que 1, X(n) se acercará para valores grandes a 1,46557^n (ver en http://oeis.org/A000930 una aproximación más precisa), y que también X(n+1)/X(n) se acercará a ese valor 1,46557. Esto segundo lo puedes ver con la hoja creando una columna de cocientes:


Función generatriz

Al igual que en las sucesiones recurrentes que ya hemos estudiado, podemos considerar una función generatriz para esta. Es la siguiente:


La comprobamos con PARI y vemos que su desarrollo contiene la sucesión en los coeficientes.

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

1 + x + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 6*x^6 + 9*x^7 + 13*x^8 + 19*x^9 + 28*x^10 + 41*x^11 + 60*x^12 + 88*x^13 + 129*x^14 + 189*x^15 + 277*x^16 + 406*x^17 + 595*x^18 + 872*x^19 + O(x^20)

En cada sucesión que estudiamos nos gusta destacar algún tipo de propiedades. En la de Narayana llaman la atención las de tipo combinatorio.

Relación con los números combinatorios

Se  X(n) equivale al número de composiciones (particiones con orden) del número n en sumandos 1 y 3. Por ejemplo, si X(7)=9, es porque existen 9 particiones ordenadas de este tipo del número 7: {1, 3, 3} {3, 1, 3} {3, 3, 1} {1, 1, 1, 1, 3} {1, 1, 1, 3, 1} {1, 1, 3, 1, 1} {1, 3, 1, 1, 1} {3, 1, 1, 1, 1} {1, 1, 1, 1, 1, 1, 1}

Con nuestra hoja “Cartesius” (no publicada) lo hemos reproducido fácilmente, con las instrucciones siguientes, que no explicaremos ahora:

XRANGO=7
XT=1,3         
SUMA=7      
REPITE        

Aquí tenemos el resultado:



Es otra forma de ver la recurrencia: estas nueve composiciones han resultado de añadir un 3 a las correspondientes a n=4, que son : {1, 3} {3, 1} y {1, 1, 1, 1} y añadir un 1 a las correspondientes a n=6: {3, 3} {1, 1, 1, 3} {1, 1, 3, 1} {1, 3, 1, 1} {3, 1, 1, 1} {1, 1, 1, 1, 1, 1}, con lo que se cumple que C(7)=C(6)+C(4). Esto ocurre para todo valor N, porque siempre podemos repartir sus composiciones entre las que terminan en 1 y las que lo hacen en 3, resultando así C(n-1) y C(n-3).

Desarrollo con binomiales

Si observas la tabla del desarrollo de X(7), entenderás que está formada por permutaciones de dos elementos (1 y 3) tomados 3, 5 o 7 veces. Las permutaciones con repetición de dos elementos equivalen a números combinatorios, por lo que podemos plantear:


En general se cumplirá:


Esto nos da un procedimiento para calcular directamente cualquier elemento de la sucesión de Narayana. La función en Basic de hoja de cálculo te lo resuelve:

Public Function narayana(n)
Dim p, q, t, s, i
 p = 0: q = n: t = 1
While p < q - 1
q = q - 2: p = p + 1 ‘Va incrementando el índice inferior y restando 2 al superior
s = 1: For i = 0 To p - 1: s = s * (q - i) / (p - i): Next i ‘Calcula el número combinatorio
t = t + s ‘Suma los números combinatorios
Wend
narayana = t
End Function

Con ella podemos responder a la cuestión de Narayana, y es que a los 20 años habría 1278 vacas.




1 comentario:

Anónimo dijo...

No se entiende nada que valores tienen cada letra