Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 223
%md
# Asymptotics and analytic combinatorics in SageMath
Daniel Krenn <sagemath@danielkrenn.at>

Part of the lecture on Analytic Combinatorics, Uppsala University, 2019-05-09
18176/9 
%md
## Introduction

Introduction

5/9 + 2019
181769\displaystyle \frac{18176}{9}
5.parent()
Integer Ring 
(5/9).parent()
Rational Field 
(2/1).parent()
Rational Field 
ZZ(2/1).parent()
Integer Ring 
2.is_unit()
False 
QQ(2).is_unit()
True 
%typeset_mode True
sqrt(2)
2\displaystyle \sqrt{2}
%typeset_mode False
sqrt(2).parent()
Symbolic Ring 
P.<z> = QQ[]
P
Univariate Polynomial Ring in z over Rational Field 
%typeset_mode True
1/(1-z)
−1z−1\displaystyle \frac{-1}{z - 1}
%typeset_mode False
(1/(1-z)).parent()
Fraction Field of Univariate Polynomial Ring in z over Rational Field 
P.<z> = QQ[[]]
P
Power Series Ring in z over Rational Field 


%typeset_mode True
1/(1-z)
1+z+z2+z3+z4+z5+z6+z7+z8+z9+z10+z11+z12+z13+z14+z15+z16+z17+z18+z19+O(z20)\displaystyle 1 + z + z^{2} + z^{3} + z^{4} + z^{5} + z^{6} + z^{7} + z^{8} + z^{9} + z^{10} + z^{11} + z^{12} + z^{13} + z^{14} + z^{15} + z^{16} + z^{17} + z^{18} + z^{19} + O(z^{20})
1/(1-z) * (1-z)
1 + O(z^20) 
SR(1/(1-z))
1+1z+1z2+1z3+1z4+1z5+1z6+1z7+1z8+1z9+1z10+1z11+1z12+1z13+1z14+1z15+1z16+1z17+1z18+1z19+O(z20)\displaystyle 1 + 1 z + 1 z^{2} + 1 z^{3} + 1 z^{4} + 1 z^{5} + 1 z^{6} + 1 z^{7} + 1 z^{8} + 1 z^{9} + 1 z^{10} + 1 z^{11} + 1 z^{12} + 1 z^{13} + 1 z^{14} + 1 z^{15} + 1 z^{16} + 1 z^{17} + 1 z^{18} + 1 z^{19} + \mathcal{O}\left(z^{20}\right)
SR(1/(1-z)) - SR(1/(1-z))  # don't use the Symbolic Ring!!!
0\displaystyle 0
%md
## Asymptotic Expansion

Asymptotic Expansion

A.<n> = AsymptoticRing('QQ^n * n^ZZ * log(n)^ZZ', QQ, default_prec=8)

1/2^n + n + O(1/n)
n+O ⁣(n−1)\displaystyle n + O\!\left(n^{-1}\right)
(n^2 + O(n)) * (n^3 + 3*n + O(1/n))
n5+O ⁣(n4)\displaystyle n^{5} + O\!\left(n^{4}\right)
log(n+1)
log⁡(n)+n−1−12n−2+13n−3−14n−4+15n−5−16n−6+17n−7−18n−8+O ⁣(n−9)\displaystyle \log\left(n\right) + n^{-1} - \frac{1}{2} n^{-2} + \frac{1}{3} n^{-3} - \frac{1}{4} n^{-4} + \frac{1}{5} n^{-5} - \frac{1}{6} n^{-6} + \frac{1}{7} n^{-7} - \frac{1}{8} n^{-8} + O\!\left(n^{-9}\right)
# we have to extend the asymptotic ring to include "e"
SCR = SR.subring(no_variables=True)
A.<n> = AsymptoticRing('QQ^n * n^ZZ * log(n)^ZZ', SCR, default_prec=8)

exp(1+1/n^2)
e+en−2+12 en−4+16 en−6+124 en−8+1120 en−10+1720 en−12+15040 en−14+O ⁣(n−16)\displaystyle e + e n^{-2} + \frac{1}{2} \, e n^{-4} + \frac{1}{6} \, e n^{-6} + \frac{1}{24} \, e n^{-8} + \frac{1}{120} \, e n^{-10} + \frac{1}{720} \, e n^{-12} + \frac{1}{5040} \, e n^{-14} + O\!\left(n^{-16}\right)
pi^(1+1/n^2)
π+πlog⁡(π)n−2+12 πlog⁡(π)2n−4+16 πlog⁡(π)3n−6+124 πlog⁡(π)4n−8+1120 πlog⁡(π)5n−10+1720 πlog⁡(π)6n−12+15040 πlog⁡(π)7n−14+O ⁣(n−16)\displaystyle \pi + \pi \log\left(\pi\right) n^{-2} + \frac{1}{2} \, \pi \log\left(\pi\right)^{2} n^{-4} + \frac{1}{6} \, \pi \log\left(\pi\right)^{3} n^{-6} + \frac{1}{24} \, \pi \log\left(\pi\right)^{4} n^{-8} + \frac{1}{120} \, \pi \log\left(\pi\right)^{5} n^{-10} + \frac{1}{720} \, \pi \log\left(\pi\right)^{6} n^{-12} + \frac{1}{5040} \, \pi \log\left(\pi\right)^{7} n^{-14} + O\!\left(n^{-16}\right)
(1 + 1/n)^n
e−12 en−1+1124 en−2−716 en−3+24475760 en−4−9592304 en−5+238043580608 en−6−67223165888 en−7+O ⁣(n−8)\displaystyle e - \frac{1}{2} \, e n^{-1} + \frac{11}{24} \, e n^{-2} - \frac{7}{16} \, e n^{-3} + \frac{2447}{5760} \, e n^{-4} - \frac{959}{2304} \, e n^{-5} + \frac{238043}{580608} \, e n^{-6} - \frac{67223}{165888} \, e n^{-7} + O\!\left(n^{-8}\right)
exp(O(1/n))
1+O ⁣(n−1)\displaystyle 1 + O\!\left(n^{-1}\right)
%md
## Harmonic Numbers

Harmonic Numbers

[harmonic_number(n) for n in srange(10)]
[0\displaystyle 0, 1\displaystyle 1, 32\displaystyle \frac{3}{2}, 116\displaystyle \frac{11}{6}, 2512\displaystyle \frac{25}{12}, 13760\displaystyle \frac{137}{60}, 4920\displaystyle \frac{49}{20}, 363140\displaystyle \frac{363}{140}, 761280\displaystyle \frac{761}{280}, 71292520\displaystyle \frac{7129}{2520}]
[sum(1/k for k in srange(1, n+1)) for n in srange(10)]
[0\displaystyle 0, 1\displaystyle 1, 32\displaystyle \frac{3}{2}, 116\displaystyle \frac{11}{6}, 2512\displaystyle \frac{25}{12}, 13760\displaystyle \frac{137}{60}, 4920\displaystyle \frac{49}{20}, 363140\displaystyle \frac{363}{140}, 761280\displaystyle \frac{761}{280}, 71292520\displaystyle \frac{7129}{2520}]
asymptotic_expansions.HarmonicNumber('n', precision=10)
log⁡(n)+γE+12n−1−112n−2+1120n−4−1252n−6+1240n−8−1132n−10+69132760n−12−112n−14+O ⁣(n−16)\displaystyle \log\left(n\right) + \gamma_E + \frac{1}{2} n^{-1} - \frac{1}{12} n^{-2} + \frac{1}{120} n^{-4} - \frac{1}{252} n^{-6} + \frac{1}{240} n^{-8} - \frac{1}{132} n^{-10} + \frac{691}{32760} n^{-12} - \frac{1}{12} n^{-14} + O\!\left(n^{-16}\right)
H_n_plus_1 = asymptotic_expansions.SingularityAnalysis('n', zeta=1, alpha=1, beta=1, precision=10)
H_n_plus_1
log⁡(n)+γE+32n−1−1312n−2+n−3−119120n−4+O ⁣(n−5log⁡(n))\displaystyle \log\left(n\right) + \gamma_E + \frac{3}{2} n^{-1} - \frac{13}{12} n^{-2} + n^{-3} - \frac{119}{120} n^{-4} + O\!\left(n^{-5} \log\left(n\right)\right)
n = H_n_plus_1.parent().gen()
H_n_plus_1.subs(n=n-1)
log⁡(n)+γE+12n−1−112n−2+1120n−4+O ⁣(n−5log⁡(n))\displaystyle \log\left(n\right) + \gamma_E + \frac{1}{2} n^{-1} - \frac{1}{12} n^{-2} + \frac{1}{120} n^{-4} + O\!\left(n^{-5} \log\left(n\right)\right)
def H(z):
    return -log(1-z) / (1-z)

P.<z> = QQ[[]]
H(z)
z+32z2+116z3+2512z4+13760z5+4920z6+363140z7+761280z8+71292520z9+73812520z10+8371127720z11+8602127720z12+1145993360360z13+1171733360360z14+1195757360360z15+2436559720720z16+4214222312252240z17+142743014084080z18+27529579977597520z19+O(z20)\displaystyle z + \frac{3}{2}z^{2} + \frac{11}{6}z^{3} + \frac{25}{12}z^{4} + \frac{137}{60}z^{5} + \frac{49}{20}z^{6} + \frac{363}{140}z^{7} + \frac{761}{280}z^{8} + \frac{7129}{2520}z^{9} + \frac{7381}{2520}z^{10} + \frac{83711}{27720}z^{11} + \frac{86021}{27720}z^{12} + \frac{1145993}{360360}z^{13} + \frac{1171733}{360360}z^{14} + \frac{1195757}{360360}z^{15} + \frac{2436559}{720720}z^{16} + \frac{42142223}{12252240}z^{17} + \frac{14274301}{4084080}z^{18} + \frac{275295799}{77597520}z^{19} + O(z^{20})
A.coefficients_of_generating_function(H, [1], precision=10, return_singular_expansions=True)
(log⁡(n)+γE+12n−1−112n−2+1120n−4+O ⁣(n−5log⁡(n))\displaystyle \log\left(n\right) + \gamma_E + \frac{1}{2} n^{-1} - \frac{1}{12} n^{-2} + \frac{1}{120} n^{-4} + O\!\left(n^{-5} \log\left(n\right)\right), {1:Tlog⁡(T)}\displaystyle \left\{1 : T \log\left(T\right)\right\})
%md
## Catalan Numbers

Catalan Numbers

[catalan_number(n) for n in srange(10)]
[1\displaystyle 1, 1\displaystyle 1, 2\displaystyle 2, 5\displaystyle 5, 14\displaystyle 14, 42\displaystyle 42, 132\displaystyle 132, 429\displaystyle 429, 1430\displaystyle 1430, 4862\displaystyle 4862]
[binomial(2*n, n) / (n+1) for n in srange(10)]
[1\displaystyle 1, 1\displaystyle 1, 2\displaystyle 2, 5\displaystyle 5, 14\displaystyle 14, 42\displaystyle 42, 132\displaystyle 132, 429\displaystyle 429, 1430\displaystyle 1430, 4862\displaystyle 4862]
b_2n_n = asymptotic_expansions.Binomial_kn_over_n('n', k=2, precision=10)
b_2n_n
1π4nn−12−18 π4nn−32+1128 π4nn−52+51024 π4nn−72−2132768 π4nn−92−399262144 π4nn−112+8694194304 π4nn−132+3932533554432 π4nn−152−3344772147483648 π4nn−172−2871740317179869184 π4nn−192+59697183274877906944 π4nn−212+84003724352199023255552 π4nn−232−3442929190570368744177664 π4nn−252−7199255611995562949953421312 π4nn−272+146315945760459007199254740992 π4nn−292+425120696706292572057594037927936 π4nn−312−687874205963671659223372036854775808 π4nn−332+O ⁣(4nn−352)\displaystyle \frac{1}{\sqrt{\pi}} 4^{n} n^{-\frac{1}{2}} - \frac{1}{8 \, \sqrt{\pi}} 4^{n} n^{-\frac{3}{2}} + \frac{1}{128 \, \sqrt{\pi}} 4^{n} n^{-\frac{5}{2}} + \frac{5}{1024 \, \sqrt{\pi}} 4^{n} n^{-\frac{7}{2}} - \frac{21}{32768 \, \sqrt{\pi}} 4^{n} n^{-\frac{9}{2}} - \frac{399}{262144 \, \sqrt{\pi}} 4^{n} n^{-\frac{11}{2}} + \frac{869}{4194304 \, \sqrt{\pi}} 4^{n} n^{-\frac{13}{2}} + \frac{39325}{33554432 \, \sqrt{\pi}} 4^{n} n^{-\frac{15}{2}} - \frac{334477}{2147483648 \, \sqrt{\pi}} 4^{n} n^{-\frac{17}{2}} - \frac{28717403}{17179869184 \, \sqrt{\pi}} 4^{n} n^{-\frac{19}{2}} + \frac{59697183}{274877906944 \, \sqrt{\pi}} 4^{n} n^{-\frac{21}{2}} + \frac{8400372435}{2199023255552 \, \sqrt{\pi}} 4^{n} n^{-\frac{23}{2}} - \frac{34429291905}{70368744177664 \, \sqrt{\pi}} 4^{n} n^{-\frac{25}{2}} - \frac{7199255611995}{562949953421312 \, \sqrt{\pi}} 4^{n} n^{-\frac{27}{2}} + \frac{14631594576045}{9007199254740992 \, \sqrt{\pi}} 4^{n} n^{-\frac{29}{2}} + \frac{4251206967062925}{72057594037927936 \, \sqrt{\pi}} 4^{n} n^{-\frac{31}{2}} - \frac{68787420596367165}{9223372036854775808 \, \sqrt{\pi}} 4^{n} n^{-\frac{33}{2}} + O\!\left(4^{n} n^{-\frac{35}{2}}\right)
n = b_2n_n.parent().gen()
b_2n_n / (n+1)
1π4nn−32−98 π4nn−52+145128 π4nn−72−11551024 π4nn−92+3693932768 π4nn−112−295911262144 π4nn−132+47354454194304 π4nn−152−3784423533554432 π4nn−172+24216965632147483648 π4nn−192−1940228990717179869184 π4nn−212+310496335695274877906944 π4nn−232−24755703131252199023255552 π4nn−252+7918382072809570368744177664 π4nn−272−640669821436755562949953421312 π4nn−292+102653487375641259007199254740992 π4nn−312−7787158293345007572057594037927936 π4nn−332+98987751948852424359223372036854775808 π4nn−352+O ⁣(4nn−372)\displaystyle \frac{1}{\sqrt{\pi}} 4^{n} n^{-\frac{3}{2}} - \frac{9}{8 \, \sqrt{\pi}} 4^{n} n^{-\frac{5}{2}} + \frac{145}{128 \, \sqrt{\pi}} 4^{n} n^{-\frac{7}{2}} - \frac{1155}{1024 \, \sqrt{\pi}} 4^{n} n^{-\frac{9}{2}} + \frac{36939}{32768 \, \sqrt{\pi}} 4^{n} n^{-\frac{11}{2}} - \frac{295911}{262144 \, \sqrt{\pi}} 4^{n} n^{-\frac{13}{2}} + \frac{4735445}{4194304 \, \sqrt{\pi}} 4^{n} n^{-\frac{15}{2}} - \frac{37844235}{33554432 \, \sqrt{\pi}} 4^{n} n^{-\frac{17}{2}} + \frac{2421696563}{2147483648 \, \sqrt{\pi}} 4^{n} n^{-\frac{19}{2}} - \frac{19402289907}{17179869184 \, \sqrt{\pi}} 4^{n} n^{-\frac{21}{2}} + \frac{310496335695}{274877906944 \, \sqrt{\pi}} 4^{n} n^{-\frac{23}{2}} - \frac{2475570313125}{2199023255552 \, \sqrt{\pi}} 4^{n} n^{-\frac{25}{2}} + \frac{79183820728095}{70368744177664 \, \sqrt{\pi}} 4^{n} n^{-\frac{27}{2}} - \frac{640669821436755}{562949953421312 \, \sqrt{\pi}} 4^{n} n^{-\frac{29}{2}} + \frac{10265348737564125}{9007199254740992 \, \sqrt{\pi}} 4^{n} n^{-\frac{31}{2}} - \frac{77871582933450075}{72057594037927936 \, \sqrt{\pi}} 4^{n} n^{-\frac{33}{2}} + \frac{9898775194885242435}{9223372036854775808 \, \sqrt{\pi}} 4^{n} n^{-\frac{35}{2}} + O\!\left(4^{n} n^{-\frac{37}{2}}\right)
def C(z):
    return (1 - sqrt(1-4*z)) / (2*z)

P.<z> = QQ[[]]

C(z)
1+z+2z2+5z3+14z4+42z5+132z6+429z7+1430z8+4862z9+16796z10+58786z11+208012z12+742900z13+2674440z14+9694845z15+35357670z16+129644790z17+477638700z18+O(z19)\displaystyle 1 + z + 2z^{2} + 5z^{3} + 14z^{4} + 42z^{5} + 132z^{6} + 429z^{7} + 1430z^{8} + 4862z^{9} + 16796z^{10} + 58786z^{11} + 208012z^{12} + 742900z^{13} + 2674440z^{14} + 9694845z^{15} + 35357670z^{16} + 129644790z^{17} + 477638700z^{18} + O(z^{19})
A.coefficients_of_generating_function(C, singularities=[1/4], precision=10)
1π4nn−32−98 π4nn−52+145128 π4nn−72−11551024 π4nn−92+3693932768 π4nn−112−295911262144 π4nn−132+47354454194304 π4nn−152−3784423533554432 π4nn−172+24216965632147483648 π4nn−192−1940228990717179869184 π4nn−212+O ⁣(4nn−11)\displaystyle \frac{1}{\sqrt{\pi}} 4^{n} n^{-\frac{3}{2}} - \frac{9}{8 \, \sqrt{\pi}} 4^{n} n^{-\frac{5}{2}} + \frac{145}{128 \, \sqrt{\pi}} 4^{n} n^{-\frac{7}{2}} - \frac{1155}{1024 \, \sqrt{\pi}} 4^{n} n^{-\frac{9}{2}} + \frac{36939}{32768 \, \sqrt{\pi}} 4^{n} n^{-\frac{11}{2}} - \frac{295911}{262144 \, \sqrt{\pi}} 4^{n} n^{-\frac{13}{2}} + \frac{4735445}{4194304 \, \sqrt{\pi}} 4^{n} n^{-\frac{15}{2}} - \frac{37844235}{33554432 \, \sqrt{\pi}} 4^{n} n^{-\frac{17}{2}} + \frac{2421696563}{2147483648 \, \sqrt{\pi}} 4^{n} n^{-\frac{19}{2}} - \frac{19402289907}{17179869184 \, \sqrt{\pi}} 4^{n} n^{-\frac{21}{2}} + O\!\left(4^{n} n^{-11}\right)
P.<z> = LazyPowerSeriesRing(QQ)
P
Lazy Power Series Ring over Rational Field 
C = P()
C.define(1 + z*C^2)
C
Uninitialized lazy power series 
C.compute_coefficients(10)
C
1 + z + 2*z^2 + 5*z^3 + 14*z^4 + 42*z^5 + 132*z^6 + 429*z^7 + 1430*z^8 + 4862*z^9 + 16796*z^10 + O(x^11) 
def Phi(u):
    return 1+u^2

expression1 = asymptotic_expansions.InverseFunctionAnalysis('n', phi=Phi, period=2, precision=10)

n = expression1.parent().gen()
expression1.subs(n=2*n+1).map_coefficients(lambda c: c.simplify())
1π4nn−32−98 π4nn−52+145128 π4nn−72−11551024 π4nn−92+O ⁣(4nn−112)\displaystyle \frac{1}{\sqrt{\pi}} 4^{n} n^{-\frac{3}{2}} - \frac{9}{8 \, \sqrt{\pi}} 4^{n} n^{-\frac{5}{2}} + \frac{145}{128 \, \sqrt{\pi}} 4^{n} n^{-\frac{7}{2}} - \frac{1155}{1024 \, \sqrt{\pi}} 4^{n} n^{-\frac{9}{2}} + O\!\left(4^{n} n^{-\frac{11}{2}}\right)
%md
## Runs in Words

Runs in Words

def denominator(z, k):
    return 1 - 2*z + z^(k+1)

P.<z> = QQ[]

denominator(z, 2).roots(CIF)
[(−1.618033988749895?\displaystyle -1.618033988749895?, 1\displaystyle 1), (0.618033988749895?\displaystyle 0.618033988749895?, 1\displaystyle 1), (1\displaystyle 1, 1\displaystyle 1)]
sorted(denominator(z, 2).roots(CIF), key=lambda (z0, m): abs(z0))
[(0.618033988749895?\displaystyle 0.618033988749895?, 1\displaystyle 1), (1\displaystyle 1, 1\displaystyle 1), (−1.618033988749895?\displaystyle -1.618033988749895?, 1\displaystyle 1)]
def dominant_singularity(k):
    return sorted(denominator(z, k).roots(CIF), key=lambda (z0, m): abs(z0))[0][0]

[dominant_singularity(k) for k in srange(1, 10)]
[1\displaystyle 1, 0.618033988749895?\displaystyle 0.618033988749895?, 0.543689012692077?\displaystyle 0.543689012692077?, 0.518790063675884?\displaystyle 0.518790063675884?, 0.508660391642005?\displaystyle 0.508660391642005?, 0.504138258361656?\displaystyle 0.504138258361656?, 0.502017055178166?\displaystyle 0.502017055178166?, 0.500994177922890?\displaystyle 0.500994177922890?, 0.500493118286553?\displaystyle 0.500493118286553?]
%md
What if $k\to\infty$?

What if k→∞k\to\infty?

A.<k> = AsymptoticRing('QQ^k * k^ZZ', QQ)

# we start with some first estimate
z0 = 1/2 + O((3/5)^k)

# fix point equation
def f(z):
    return (1+z^(k+1)) / 2

f(z0)
12+14(12)k+O ⁣((310)kk)\displaystyle \frac{1}{2} + \frac{1}{4} \left(\frac{1}{2}\right)^{k} + O\!\left(\left(\frac{3}{10}\right)^{k} k\right)
f(f(z0))
12+14(12)k+18(14)kk+18(14)k+O ⁣((320)kk2)\displaystyle \frac{1}{2} + \frac{1}{4} \left(\frac{1}{2}\right)^{k} + \frac{1}{8} \left(\frac{1}{4}\right)^{k} k + \frac{1}{8} \left(\frac{1}{4}\right)^{k} + O\!\left(\left(\frac{3}{20}\right)^{k} k^{2}\right)
f(f(f(z0)))
12+14(12)k+18(14)kk+18(14)k+332(18)kk2+532(18)kk+116(18)k+O ⁣((340)kk3)\displaystyle \frac{1}{2} + \frac{1}{4} \left(\frac{1}{2}\right)^{k} + \frac{1}{8} \left(\frac{1}{4}\right)^{k} k + \frac{1}{8} \left(\frac{1}{4}\right)^{k} + \frac{3}{32} \left(\frac{1}{8}\right)^{k} k^{2} + \frac{5}{32} \left(\frac{1}{8}\right)^{k} k + \frac{1}{16} \left(\frac{1}{8}\right)^{k} + O\!\left(\left(\frac{3}{40}\right)^{k} k^{3}\right)
f(f(f(f(z0))))
12+14(12)k+18(14)kk+18(14)k+332(18)kk2+532(18)kk+116(18)k+112(116)kk3+316(116)kk2+1396(116)kk+132(116)k+O ⁣((380)kk4)\displaystyle \frac{1}{2} + \frac{1}{4} \left(\frac{1}{2}\right)^{k} + \frac{1}{8} \left(\frac{1}{4}\right)^{k} k + \frac{1}{8} \left(\frac{1}{4}\right)^{k} + \frac{3}{32} \left(\frac{1}{8}\right)^{k} k^{2} + \frac{5}{32} \left(\frac{1}{8}\right)^{k} k + \frac{1}{16} \left(\frac{1}{8}\right)^{k} + \frac{1}{12} \left(\frac{1}{16}\right)^{k} k^{3} + \frac{3}{16} \left(\frac{1}{16}\right)^{k} k^{2} + \frac{13}{96} \left(\frac{1}{16}\right)^{k} k + \frac{1}{32} \left(\frac{1}{16}\right)^{k} + O\!\left(\left(\frac{3}{80}\right)^{k} k^{4}\right)