# MAKE SURE TO RUN THIS CELL!
var('w x y z r s i j')

(w, x, y, z, r, s, i, j)

# Sage has good built-in support for (univariate) asymptotics through the AsymptoticRing structure
SCR = SR.subring(no_variables=True) # Create symbolic ring with no variables
A.<n> = AsymptoticRing(
    growth_group='QQ^n * n^QQ * log(n)^QQ', 
    coefficient_ring=SCR,
    default_prec=4
)
A

Asymptotic Ring <QQ^n * n^QQ * log(n)^QQ * Signs^n> over Symbolic Constants Subring

# When n generates an AsymptoticRing, Sage automatically computes expansions
show(SR("sqrt(1+n)"), " = \t", sqrt(1+n))
show(SR("(1+1/n)^n"), " = \t", (1+1/n)^n)
show(SR("log(1+n)"), " = \t", log(1+n))

# The package can compute asymptotic expansions of meromorphic functions from its singularities
# using the results discussed in this chapter
def GF(z):
    return 1/((1-2*z)^2*(1+z))

asm = A.coefficients_of_generating_function(
    function=GF,
    singularities=(1/2,),
    precision=3
)
show("[z^n]", SR("1/((1-2*z)^2*(1+z))"), " = \t", asm)

# It can also compute expansions near logarithmic and algebraic singularities using transfer theorems
def harmonic(z):
    return - log(1 - z) / (1 - z)

asm = A.coefficients_of_generating_function(
    function=harmonic,
    singularities=(1,),
    precision=10
)
show("[z^n]", SR("- log(1 - z) / (1 - z)"), " = \t", asm)


def catalan(z):
    return (1-sqrt(1-4*z))/(2*z)
asm = A.coefficients_of_generating_function(
    function=catalan,
    singularities=(1/4,),
    precision=3
)
show("[z^n]", SR("(1-sqrt(1-4*z))/(2*z)"), " = \t", asm)

# Sage can compute partial fraction decompositions for rational functions
F = (3*z+4)/(-6*z^5 + 13*z^4 - 4*z^3 - 6*z^2 + 2*z + 1)
show(F, " = \t", F.partial_fraction())

# It can also compute residues
F = tan(z)
show("The residue of \t", F, " at z = pi/2 is", F.residue(z==pi/2))

# Note that Sage does not know there is an exponentially smaller error
def surjection(z):
    return 1/(2-exp(z))

asm = A.coefficients_of_generating_function(
    function=surjection,
    singularities=(log(2),),
    precision=10
)
show("[z^n]", SR("1/(2-exp(z))"), " = \t", asm)

# These asymptotic expansions can be computed automatically in Sage
def algsing(z):
    return (1-z)^(-3/2)

asm = A.coefficients_of_generating_function(
    function=algsing,
    singularities=(1,),
    precision=10
)
show("[z^n]", SR("(1-z)^(-3/2)"), " = \t", asm)

# These asymptotic expansions can be computed automatically in Sage
def EvenCycles(z):
    return exp(-z/2)/sqrt(1-z)

asm = A.coefficients_of_generating_function(
    function=EvenCycles,
    singularities=(1,),
    precision=3
)
show("[z^n]", SR("exp(-z/2)/sqrt(1-z)"), " = \t", asm)

# These asymptotic expansions can be computed automatically in Sage
def TwoRegular(z):
    return exp(-z/2-z^2/4)/sqrt(1-z)

asm = A.coefficients_of_generating_function(
    function=TwoRegular,
    singularities=(1,),
    precision=3
)
show("[z^n]", SR("exp(-z/2)/sqrt(1-z)"), " = \t", asm)

# Copied from above
def catalan(z):
    return (1-sqrt(1-4*z))/(2*z)

asm = A.coefficients_of_generating_function(
    function=catalan,
    singularities=(1/4,),
    precision=3
)
show("[z^n]", SR("(1-sqrt(1-4*z))/(2*z)"), " = \t", asm)

var('n')
F = exp(z/(1-z))
coeffs = list(F.series(z,100).truncate().polynomial(QQ))
asm = n^(-3/4)*exp(2*sqrt(n))/sqrt(4*pi*exp(1))
print("We have shown in the book that")
show("[z^n]", SR("exp(z/(1-z))"), " ~ \t", asm)

We have shown in the book that

# Here we plot the ratio of the EGF coefficients to the predicted asymtptotic behaviour
line([[k,coeffs[k]/asm.subs(n=k)] for k in range(1,100)])

var('n')
F = exp(z + z^2/2)
coeffs = list(F.series(z,100).truncate().polynomial(QQ))
asm = n^(n/2)*exp(sqrt(n)-n/2)/sqrt(2*exp(1/2))
print("We have shown in the book that")
show("[z^n]", SR("exp(z + z^2/2)"), " ~ \t", asm)

We have shown in the book that

# Here we plot the ratio of the EGF coefficients to the predicted asymtptotic behaviour
line([[k,factorial(k)*coeffs[k]/asm.subs(n=k)] for k in range(1,100)])

This notebook contains worked examples from Chapter 3 of the text Analytic Combinatorics in Several Variables (2nd edition) by Pemantle, Wilson and Melczer.¶

Asymptotic Expansions in Sage¶

Partial Fractions and Residues¶

Example 3.8 - Surjections¶

Lemma 3.10 - Basic Scale¶

Example 3.11 - Darboux Example¶

Example 3.13 - 2-Regular Graphs¶

Example 3.16 - Catalan Numbers¶

Example 3.18 - Ordered Set Partitions¶

Example 3.19 - involutions¶