Erzeugende Funktion der Fibonacci-Folge series(1/(1-z-z^2),z,30);

K1tvSSJ6RzYiIiIiIiIhRiVGJSIiI0YnIiIkRigiIiYiIiUiIilGKSIjOCIiJyIjQCIiKCIjTUYrIiNiIiIqIiMqKSIjNSIkVyIiIzYiJEwjIiM3IiR4JEYsIiQ1JyIjOSIkKCkqIiM6IiUoZiIiIzsiJSVlIyIjPCIlIj0lIiM9IiVsbiIjPiImWTQiIiM/IiY2eCJGLiImZCdHIiNBIiZvaiUiI0IiJkRdKCIjQyInJFJAIiIjRCInPWs+IiNFIic2eUoiI0YiJ0hVXiIjRyInUz8kKSIjSC1JIk9HJSpwcm90ZWN0ZWRHNiNGJSIjSQ==

Partialbruchzerlegung convert(1/(1-z-z^2),parfrac,z=0,sqrt(5));

LCYqKCMiIiMiIiYiIiIpRiYjRidGJUYnLCgqJkYlRidJInpHNiJGJyEiIkYnRi4qJEYoRidGJ0YuRicqKEYkRidGKEYnLChGK0YnRidGJ0YvRidGLkYn

Entwickelt man davon den ersten Summanden, sieht man, dass Runden zur n\303\244chsten ganzen Zahl die Fibonacci Zahlen liefert evalf(series((2/5)*sqrt(5)/(-2*z-1+sqrt(5)),z=0,20));

K01JInpHNiIkIishKXoxT3MhIzUiIiEkIislUj8zPCIhIioiIiIkIisjPkZXKj1GKyIiIyQiKyplWl8xJEYrIiIkJCIrJnl1J2ZcRisiIiUkIit5QiNcLSlGKyIiJiQiKzwoZiUpSCIhIikiIickIitjPiY0NSNGOyIiKCQiK3U7VCpSJEY7IiIpJCIrTE9PK2JGOyIiKiQiKztgeCoqKSlGOyIjNSQiKyYqUSxTOSEiKCIjNiQiK0Y5KipIQkZLIiM3JCIrRmArcVBGSyIjOCQiK2VuKioqNCdGSyIjOSQiKykzLSsoKSpGSyIjOiQiKyYpKSoqcGYiISInIiM7JCIrJjQrU2UjRmVuIiM8JCIrJCkqKio0PSVGZW4iIz0kIiskMytddydGZW4iIz4tSSJPRyUqcHJvdGVjdGVkRzYjRiwiIz8=

Entwickelt man den zweiten Summanden, sieht man die Gr\303\266\303\237e des Fehlers (stets < 1/2) evalf(series((2/5)*sqrt(5)/(2*z+1+sqrt(5)),z=0,20));

K01JInpHNiIkIitBPyRSdyMhIzUiIiEkIStMUj8zPEYnIiIiJCIrITRHZDAiRiciIiMkIStFJWVaXychIzYiIiQkIit4Q19LU0YxIiIlJCErYGZCI1wjRjEiIiYkIitFbEdTOkYxIiInJCErZFVcPiYqISM3IiIoJCIrNDVQJCllRj4iIikkISteSzdPT0Y+IiIqJCIrZXhDWkFGPiIjNSQhKydcdikpUSJGPiIjNiQiK0RFcyRlKSEjOCIjNyQhK01CLjBgRk4iIzgkIislSCFweUtGTiIjOSQhK1M/TUU/Rk4iIzokIithI1tCRCJGTiIjOyQhK3R5JCpSeCEjOSIjPCQiK3VZYSR5JUZobiIjPSQhKyc+JFJjSEZobiIjPi1JIk9HJSpwcm90ZWN0ZWRHNiNGKyIjPw==

Zerlegung des Z\303\244hlers und exakte Formel tau:=[solve(1-z-z^2,z)];

NyQsJiomIyIiIiIiI0YmKSIiJkYlRiYhIiJGJUYqLCZGJEYmRiVGKg==

simplify(tau[1]*tau[2]);

ISIi

t:=tau[2];

LCYqJiMiIiIiIiNGJSkiIiZGJEYlRiVGJCEiIg==

Exakte Formel (Achtung, da war ein Fehler in der Vorlesung!) seq(simplify((1/(1+t^2)*1/t^n+1/(t^(-2)+1)*(-t)^n)),n=0..10);

Ni0iIiJGIyIiIyIiJCIiJiIiKSIjOCIjQCIjTSIjYiIjKik=

Zum Millionenbeispiel, xi_1,...,xi_4 sind die Nullstellen von 1+z+z^2+z^3+z^4. Es ist xi_1=xi und alle anderen xi_j=xi^j sind Potenzen davon! alias(xi=RootOf(1+z+z^2+z^3+z^4));

SSN4aUc2Ig==

simplify(xi^5); evalf(xi-exp(2*I*Pi/5));

IiIi

LCYkIiIiISM/RiQqJiQiIiFGKEYkXiNGJEYkRiQ=

Also ist xi=exp(2*I*Pi/5); Vollst\303\244ndige Partialbruchzerlegung von P(z) in ihrer ganzen Scheu\303\237lichkeit. (Beachte 1+xi^1+xi^2+xi^3=-xi^4) (convert(1/ ( (1-z)*(1-z^5)*(1-z^10) ),parfrac,xi));

LEIqJiMiIiIiI1NGJSwmSSJ6RzYiRiVGJUYlISIiRiUqKCNGJSIkXSNGJSwqKiYiIiNGJSlJI3hpR0YpIiIkRiVGKiomIiIlRiUpRjJGMEYlRipGMkYqRjNGKkYlKSwmKiRGNkYlRiVGKEYqRjBGKkYlKihGLEYlLCoqJkY1RiVGMUYlRiUqJkYzRiVGNkYlRiUqJkYwRiVGMkYlRiVGJUYlRiUpLCwqJEYxRiVGJUY5RiVGMkYlRihGJUYlRiVGMEYqRiUqKiNGJSIjP0YlRjJGJSwmRjlGJUYlRiVGJSwsRkFGJUY5RiVGMkYlRihGKkYlRiVGKkYlKiYjRiUiI11GJSksJkYlRipGKEYlRjNGKkYqKigjRiUiJCsmRiUsKiomIiNYRiVGMkYlRiUiIzZGKiomIiM4RiVGMUYlRiUqJiIjR0YlRjZGJUYlRiUsJkYoRipGMkYlRipGJSooRk1GJSwqKiYiIzxGJUYxRiVGJSomIiNLRiVGNkYlRiVGUEYlIiNjRiVGJUZARipGJSooRkNGJSwoRjlGJUYyRiVGJUYlRiUsJkY5RiVGKEYlRipGJSooRkNGJSwoRkFGJUYyRiVGJUYlRiUsJkYoRiVGMkYlRipGJSooRixGJSwqRj5GKkYlRipGQUYlKiZGMEYlRjZGJUYlRiUpRldGMEYqRiUqJiMiI3giJCsjRiVGS0YqRioqKEZNRiUsKiomRmduRiVGMUYlRiUqJkZURiVGNkYlRioqJiIjOkYlRjJGJUYlIiNDRipGJSwmRkFGJUYoRipGKkYlKiYjRlQiJCsiRiUpRktGMEYqRiUqKEYsRiUsKkYyRiVGMEYqKiZGM0YlRjFGJUYqRjlGKkYlKUZecEYwRipGJSooRk1GJSwqIiNSRioqJkZWRiVGMUYlRioqJkZlbkYlRjZGJUYlRltwRipGJUY4RipGJSoqRkNGJUYyRiUsJkYlRiVGMkYlRiUsJkZBRiVGKEYlRipGKg==

evalf(%);

LEIqJiQiNSsrKysrKysrK0QhI0AiIiIsJkkiekc2IkYnJEYnIiIhRichIiJGJyomLCYkIjUjUnomKipcJmY4cyVwRiZGLSomJCI1aVcoelk8cygqb1YjRiZGJ14jRidGJ0YnRicsJiwmJCI1NkN1JVxQJSpwLDQpISM/Ri0qJiQiNTxISlojSF9feShlRjpGJ0Y1RidGJ0YnKiZGK0YnRilGJ0YtRi1GJyomLCYkIjUzMVUrXS9reV9nRiZGLSomJCI1UDohUWAuVydHSzVGOkYnRjVGJ0YnRicsJkY+Ri0sJiQiNTVDdSVcUCUqcCw0JEY6RicqJiQiNTdzTjomSDtsMF4qRjpGJ0Y1RidGJ0YnRi1GJyomLCYkIjU/W1sqKVwoKSlSLj0nISNBRicqJiQiNTtLKlI/TjMzbF0pRlFGJ0Y1RidGLUYnKUY2IiIjRi1GJyomJCI1KysrKysrKysrP0YmRicpLCZGK0YtRilGJyIiJEYtRi0qJiwmJCI1I1tbKilcKCkpUi49O0YmRi0qJiQiNSsxTzg+QDZKZF9GUUYnRjVGJ0YnRicpLCYsJiQiNTZDdSVcUCUqcCw0JEY6Ri0qJiQiNTZzTjomSDtsMF4qRjpGJ0Y1RidGJ0YnRilGJ0ZWRi1GJyomLCZGaW5GLSomJCI1LzFPOD5ANkpkX0ZRRidGNUYnRi1GJylGRkZWRi1GJyomLCYkIjUvMVUrXS9reV9nRiZGJyomJCI1TzohUWAuVydHSzVGOkYnRjVGJ0YnRidGX29GLUYnKiYsJkYkRicqJiQiNWxdTCJRSCUpM1VwKEYmRidGNUYnRidGJywmRjdGJ0YpRidGLUYnKiYsJkYkRi0qJiQiNVpALU0sP2pOOz1GJkYnRjVGJ0YnRicsJkZgb0YnRj5GLUYtRicqJiQiNSsrKysrKysrXVFGOkYnRmVuRi1GLSomLCZGJEYnRmVwRi1GJywmLCYkIjU1Q3UlXFAlKnAsNClGOkYtKiYkIjU9SEpaI0hfX3koZUY6RidGNUYnRi1GJ0YpRidGLUYnKiYkIjUrKysrKysrKys4RjpGJylGZW5GVkYtRicqJiwmRjBGLUYyRi1GJywmRmVxRidGPkYtRi1GJyomLCZGT0YnRlJGJ0YnKUZhckZWRi1GJyomLCZGJEYnRltxRidGJywmRilGJ0ZHRidGLUYn

Digits:=4: series(1/ ( (1-z)*(1-z^5)*(1-z^10)) ,z,101);

K2l3SSJ6RzYiIiIiIiIhRiVGJUYlIiIjRiUiIiRGJSIiJUYnIiImRiciIidGJyIiKEYnIiIpRiciIipGKSIjNUYpIiM2RikiIzdGKSIjOEYpIiM5RisiIzpGKyIjO0YrIiM8RisiIz1GKyIjPkYuIiM/Ri4iI0BGLiIjQUYuIiNCRi4iI0NGMSIjREYxIiNFRjEiI0ZGMSIjR0YxIiNIRjUiI0lGNSIjSkY1IiNLRjUiI0xGNSIjTUY5IiNORjkiI09GOSIjUEY5IiNRRjkiI1JGPiIjU0Y+IiNURj4iI1VGPiIjVkY+IiNXRkMiI1hGQyIjWUZDIiNaRkMiI1tGQyIjXEZJIiNdRkkiI15GSSIjX0ZJIiNgRkkiI2FGTyIjYkZPIiNjRk8iI2RGTyIjZUZPIiNmRlYiI2dGViIjaEZWIiNpRlYiI2pGViIja0ZnbiIjbEZnbiIjbUZnbiIjbkZnbiIjb0ZnbiIjcEZfbyIjcUZfbyIjckZfbyIjc0ZfbyIjdEZfbyIjdUZnbyIjdkZnbyIjd0ZnbyIjeEZnbyIjeUZnbyIjeiIjIikiIyEpRl9wRl9wRl9wIiMjKUZfcCIjJClGX3AiIyUpIiMhKiIjJilGZHAiIycpRmRwIiMoKUZkcCIjKSlGZHAiIyopIiQrIkZkcEZqcCIjIipGanAiIyMqRmpwIiMkKkZqcCIjJSoiJDUiIiMmKkZfcSIjJypGX3EiIygqRl9xIiMpKkZfcSIjKioiJEAiRmpwLUkiT0clKnByb3RlY3RlZEc2I0YlIiQsIg==

P:=convert(series(1/ ( (1-z)*(1-z^5)*(1-z^10)) ,z,10001),polynom): The actual numbers p(n) for n=10,100,1000 and 10000 and the asymptotic estimates by n^2/100: For n=10000 the relative error is 2001/1002001 < 0.2%. Not too bad! seq(coeff(P,z,n),n in [10,100,1000,10000]);

NiYiIiUiJEAiIiYsLSIiKCw/KyI=

seq(n^2/100,n in [10,100,1000,10000]);

NiYiIiIiJCsiIiYrKyIiKCsrKyI=

The binary trees example solve(A=1+z*A^2,A);

NiQsJCooIyIiIiIiI0YmSSJ6RzYiISIiLCZGJkYmKiQpLCZGJkYmKiYiIiVGJkYoRiZGKkYlRiZGJkYmRiYsJCooRiVGJiwmRiZGKkYsRiZGJkYoRipGKg==

T:=%[2];

LCQqKCMiIiIiIiNGJSwmRiUhIiIqJCksJkYlRiUqJiIiJUYlSSJ6RzYiRiVGKEYkRiVGJUYlRi5GKEYo

series(T,z=0,12);

Kz1JInpHNiIiIiIiIiFGJUYlIiIjRiciIiYiIiQiIzkiIiUiI1VGKCIkSyIiIiciJEglIiIoIiVJOSIiKSIlaVsiIioiJid6OyIjNSImJ3llIiM2LUkiT0clKnByb3RlY3RlZEc2I0YlIiM3

Iterative solution of the binary tree functional equation A:=0: N:=10: for i from 0 to N do A:=(1+z*A^2): print(series(A,z=0,i+2)): od:

KyVJInpHNiIiIiIiIiE=

KydJInpHNiIiIiIiIiFGJUYl

KytJInpHNiIiIiIiIiFGJUYlIiIjRidGJSIiJA==

Ky9JInpHNiIiIiIiIiFGJUYlIiIjRiciIiYiIiQiIiciIiUtSSJPRyUqcHJvdGVjdGVkRzYjRiVGKA==

KzFJInpHNiIiIiIiIiFGJUYlIiIjRiciIiYiIiQiIzkiIiUiI0VGKC1JIk9HJSpwcm90ZWN0ZWRHNiNGJSIiJw==

KzNJInpHNiIiIiIiIiFGJUYlIiIjRiciIiYiIiQiIzkiIiUiI1VGKCIkKyIiIictSSJPRyUqcHJvdGVjdGVkRzYjRiUiIig=

KzVJInpHNiIiIiIiIiFGJUYlIiIjRiciIiYiIiQiIzkiIiUiI1VGKCIkSyIiIiciJGwkIiIoLUkiT0clKnByb3RlY3RlZEc2I0YlIiIp

KzdJInpHNiIiIiIiIiFGJUYlIiIjRiciIiYiIiQiIzkiIiUiI1VGKCIkSyIiIiciJEglIiIoIiUtOCIiKS1JIk9HJSpwcm90ZWN0ZWRHNiNGJSIiKg==

KzlJInpHNiIiIiIiIiFGJUYlIiIjRiciIiYiIiQiIzkiIiUiI1VGKCIkSyIiIiciJEglIiIoIiVJOSIiKSIlMVkiIiotSSJPRyUqcHJvdGVjdGVkRzYjRiUiIzU=

KztJInpHNiIiIiIiIiFGJUYlIiIjRiciIiYiIiQiIzkiIiUiI1VGKCIkSyIiIiciJEglIiIoIiVJOSIiKSIlaVsiIioiJiVHOyIjNS1JIk9HJSpwcm90ZWN0ZWRHNiNGJSIjNg==

Kz1JInpHNiIiIiIiIiFGJUYlIiIjRiciIiYiIiQiIzkiIiUiI1VGKCIkSyIiIiciJEglIiIoIiVJOSIiKSIlaVsiIioiJid6OyIjNSImaXgmIiM2LUkiT0clKnByb3RlY3RlZEc2I0YlIiM3

5-ary trees A:=0: N:=10: for i from 0 to N do A:=(1+z*A^5): print(series(A,z=0,i+2)): od:

KyVJInpHNiIiIiIiIiE=

KydJInpHNiIiIiIiIiFGJUYl

Ky1JInpHNiIiIiIiIiFGJUYlIiImIiIjIiM1IiIkLUkiT0clKnByb3RlY3RlZEc2I0YlIiIl

Ky9JInpHNiIiIiIiIiFGJUYlIiImIiIjIiNOIiIkIiRnIiIiJS1JIk9HJSpwcm90ZWN0ZWRHNiNGJUYn

KzFJInpHNiIiIiIiIiFGJUYlIiImIiIjIiNOIiIkIiQmRyIiJSIlMD5GJy1JIk9HJSpwcm90ZWN0ZWRHNiNGJSIiJw==

KzNJInpHNiIiIiIiIiFGJUYlIiImIiIjIiNOIiIkIiQmRyIiJSIlSURGJyImRTEjIiInLUkiT0clKnByb3RlY3RlZEc2I0YlIiIo

KzVJInpHNiIiIiIiIiFGJUYlIiImIiIjIiNOIiIkIiQmRyIiJSIlSURGJyImXlAjIiInIidiaUAiIigtSSJPRyUqcHJvdGVjdGVkRzYjRiUiIik=

KzdJInpHNiIiIiIiIiFGJUYlIiImIiIjIiNOIiIkIiQmRyIiJSIlSURGJyImXlAjIiInIichKT1CIiIoIig/QkQjIiIpLUkiT0clKnByb3RlY3RlZEc2I0YlIiIq

KzlJInpHNiIiIiIiIiFGJUYlIiImIiIjIiNOIiIkIiQmRyIiJSIlSURGJyImXlAjIiInIichKT1CIiIoIihYL0wjIiIpIilJKGZOIyIiKi1JIk9HJSpwcm90ZWN0ZWRHNiNGJSIjNQ==

KztJInpHNiIiIiIiIiFGJUYlIiImIiIjIiNOIiIkIiQmRyIiJSIlSURGJyImXlAjIiInIichKT1CIiIoIihYL0wjIiIpIiliLiZSIyIiKiIqWC1mWyMiIzUtSSJPRyUqcHJvdGVjdGVkRzYjRiUiIzY=

Kz1JInpHNiIiIiIiIiFGJUYlIiImIiIjIiNOIiIkIiQmRyIiJSIlSURGJyImXlAjIiInIichKT1CIiIoIihYL0wjIiIpIiliLiZSIyIiKiIqcUxhXSMiIzUiKzBEP1xFIiM2LUkiT0clKnByb3RlY3RlZEc2I0YlIiM3

Bar graph perimeter generating function solve(B=1/(1-z^2)*1/(1-( z^2*B/(1-z^2) ))*(1+B)*z^2-z^2,B );

NiQsJCooIyIiIiIiI0YmKUkiekc2IkYnISIiLCoqJClGKSIiJUYmRisqJkYnRiZGKEYmRitGJkYmKiQpLCoqJClGKSIiKUYmRiYqJkYnRiZGLkYmRiYqJkYvRiZGKEYmRitGJkYmRiVGJkYmRiZGJiwkKihGJUYmLCpGLUYmRjBGJkYxRiZGJkYrRiZGKEYrRis=

series(%[2],z,20);

KzNJInpHNiIiIiIiIiUiIiMiIiciIiYiIikiIzgiIzUiI04iIzciIygqIiM5IiR2IyIjOy1JIk9HJSpwcm90ZWN0ZWRHNiNGJSIjPQ==

The perimeter is always even, so look at half-perimeter g.f. B(sqrt(z)) solve(z^4+2*z^2-4*z+1);

NiYiIiIsKComI0YjIiIkRiMpLCYiI0VGIyomIiInRiMpIiNMI0YjIiIjRiNGI0YmRiNGIyomIyIiKUYnRiNGKCEiIkY0RiZGNCwqKiYjRiNGLEYjRihGI0Y0KiYjIiIlRidGI0YoRjRGI0YmRjQqKComRi9GI14jRiNGI0YjKUYnRi9GIywmRiVGI0YxRiNGI0YjLCpGNkY0RjhGI0YmRjQqKCwkRjxGI0YjRj5GI0Y/RiNGNA==

simplify((z^4+2*z^2-4*z+1)/(1-z));

LCoqJClJInpHNiIiIiQiIiIhIiIqJClGJSIiI0YoRikqJkYnRihGJUYoRilGKEYo

Dominant singularity is the smallest positive zero of this polynomial: solve(-z^3-z^2-3*z+1);

NiUsKCokLCYiI0UiIiIqJCIjTCNGJyIiIyIiJyNGJyIiJEYtKiRGJSMhIiJGLiMhIilGLkYwRicsKkYkI0YxRixGLyMiIiVGLkYwRicqKF4jRipGJ0YuRiosJkYkRi1GLyMiIilGLkYnRicsKkYkRjVGL0Y2RjBGJyooXiMjRjFGK0YnRi5GKkY6RidGJw==

evalf(%);

NiUkIitEdShmJkghIzVeJCQhKzooKSl6WidGJSQiK1FLVkA8ISIqXiRGJyQhK1FLVkA8Ris=

Restricted MSET constructions: simplify(series(exp(add(u^k*B(z^k)/k,k=1..10)),u,5));

Ky9JInVHNiIiIiIiIiEtSSJCR0YkNiNJInpHRiRGJSwmLUYoNiMqJEYqIiIjI0YlRi8qJEYnRi9GMEYvLCgtRig2IyokRioiIiQjRiVGNiomRidGJUYsRiVGMCokRidGNiNGJSIiJ0Y2LCwtRig2IyokRioiIiUjRiVGQComRidGJUYzRiVGNyokRixGLyNGJSIiKSomRixGJUYnRi9GQSokRidGQCNGJSIjQ0ZALUkiT0clKnByb3RlY3RlZEc2I0YlIiIm

For unary - binary trees this gives the functional equation B(z)=z*(1+B(z)+((1/2)*B(z^2)+(1/2)*B(z)^2)), which is equivalent to B(z)=RHS with RHS as below. This is exploited in the "asymptotics" section. RHS:=solve(B(z)=z*(1+B(z)+((1/2)*B(z^2)+(1/2)*B(z)^2)),B(z))[2];

LCQqJiwoSSJ6RzYiIiIiISIiRicqJCwqKiYtSSJCR0YmNiMqJEYlIiIjRidGJUYwRihGL0YoRiUhIiNGJ0YnI0YnRjBGJ0YnRiVGKEYo

The g.f. of ordered unary-binary trees. solve(T=z*(1+T+T^2),T);

NiQsJCooIyIiIiIiI0YmSSJ6RzYiISIiLChGKEYqRiZGJiokKSwoKiYiIiRGJilGKEYnRiZGKiomRidGJkYoRiZGKkYmRiZGJUYmRiZGJkYmLCQqKEYlRiYsKEYoRiZGJkYqRixGJkYmRihGKkYq

JSFH Functional equation for ordered trees without restrictions on the degree solve(s=z/(1-s),s);

NiQsJiMiIiIiIiNGJSomRiRGJSksJkYlRiUqJiIiJUYlSSJ6RzYiRiUhIiJGJEYlRiUsJkYkRiVGJ0Yu

The following is the number of nodes and root degree g.f. of ordered trees. simplify(z/(1-u*(1/2-(1/2)*sqrt(1-4*z) )));

LCQqJkkiekc2IiIiIiwoKiZJInVHRiVGJiwmRiZGJkYkISIlI0YmIiIjRiZGKSEiIkYtRiZGLkYt

simplify(series(%,z,10));

KzdJInpHNiIiIiJGJUkidUdGJCIiIywmKiRGJkYnRiVGJkYlIiIkLCgqJEYmRipGJUYpRidGJkYnIiIlLCoqJEYmRi1GJUYsRipGKSIiJkYmRjBGMCwsKiRGJkYwRiVGL0YtRiwiIipGKSIjOUYmRjQiIicsLiokRiZGNUYlRjJGMEYvRjRGLCIjR0YpIiNVRiZGOSIiKCwwKiRGJkY6RiVGN0Y1RjIiIz9GLyIjW0YsIiMhKkYpIiRLIkYmRkAiIiksMiokRiZGQUYlRjxGOkY3IiNGRjIiI3ZGLyIkbCJGLCIkKEhGKSIkSCVGJkZIRjMtSSJPRyUqcHJvdGVjdGVkRzYjRiUiIzU=

JSFH