# We begin by defining some helper functions for below
# MAKE SURE TO RUN THIS CELL!
var('w x y z r s i j')

def GFinfo(F, z=z, exponential=False, OEIS=False):    
    if exponential==False:
        show("This generating function has the expansion")
        show(F, "=\t", F.series(z,10))
    else:
        pol = F.series(z,10).truncate().polynomial(QQ)
        terms = [[pol[k],"\\frac{" + latex(pol[k]*factorial(k)) + "}{" + k + "!} \cdot" + latex(z^k)] for k in range(10)]
        nz_terms = [st for (p,st) in terms if p != 0]
        st = ''
        for k in nz_terms[0:-1]: st += k + " + "
        show("This exponential generating function has an expansion beginning")
        show(F, "=\t", st + nz_terms[-1])
        
    if OEIS==True:
        print("The OEIS has the following entry for this starting sequence")
        oeis(list(F.series(z,10).truncate().polynomial(QQ)))
        
def GFinfo2D(F, var1=x, var2=y, semi=False):    
    if semi==False:
        show("The initial array of coefficients for this generating function is")
        ser = QQ[var1,var2](F.taylor((var1,0), (var2,0), 17))
        show(matrix([[ser[i,j] for i in range(8)] for j in range(8)]))
    else:
        pol = QQ[var1,var2](F.taylor((var1,0), (var2,0), 21))
        terms = [[pol[k,n-k],"\\frac{" + latex(pol[k,n-k]*factorial(n-k)) + "}{" + (n-k) + "!} \cdot" + latex(var1^k*var2^(n-k))] for n in range(10) for k in range(n+1)]
        nz_terms = [st for (p,st) in terms if p != 0]
        st = ''
        for k in nz_terms[0:-1]: st += k + " + "
        show("This exponential generating function has an expansion beginning")
        show(F, "=\t", st + nz_terms[-1])

GFinfo(1/(1-z-z^2))

GFinfo2D(1/(1-x-y))
show("This equals the expected coefficients")
show(matrix([[binomial(i+j,i) for i in range(8)] for j in range(8)]))

GFinfo2D(1/(1-x-x*y))

GFinfo2D(1/(1-x-y-x*y))

# Build the generating function in the book
var('x y z w')
G1 = x*y*z*w
G2 = x^2*y*z*w
G3 = x*y*z*w*(x*y+x^2*y*z)/(1-x^2*y*z)
G4 = x*y*z*w*(x*z+x^2*y*z)/(1-x^2*y*z)
G = G1+G2+G3+G4
F = (1/(1-G) - 1)/(x*y*z*w)

# Find initial terms in the expansion
show("The series expansion of the generating function")
show(F.numerator().expand()/F.denominator().expand())
show("begins \t", F.taylor(x,0,2).expand())

A = Matrix([[1,1],[1,0]])
print("The matrix containing the generating functions enumerating binary strings without consecutive 1s by starting and ending symbol is")
show((matrix.identity(2) - z*A).inverse().simplify_full())

The matrix containing the generating functions enumerating binary strings without consecutive 1s by starting and ending symbol is

dim = 4
Z = var('Z', n=dim)
F = 1/(1-add([Z[k]/(1+Z[k]) for k in range(dim)]))
print("The generating function for Smirnov words in dimension {} is".format(dim))
show(F)
print("and its series expansion at the origin begins")
R = QQ[[Z]]
show(R(F.numerator())/(R(F.denominator()) + O(R(Z[0]^5))))

The generating function for Smirnov words in dimension 4 is

and its series expansion at the origin begins

C = (1 - sqrt(1-4*z))/(2*z)
print("The Catalan generating function is")
show(C)
GFinfo(C)

The Catalan generating function is

F = 2/(1+sqrt(1-x)-y)
print("The generating function for this sequence is")
show(F)
GFinfo2D(F)

# Compute starting terms in sequence using recursion 
@cached_function
def rec_a(r,s):
    if (r<0 or s<0):
        return 0
    elif (r==0 and s==0):
        return 1
    else:
        return (rec_a(r,s-1) + rec_a(r-1,s+1))/2

print("This matches the terms computed from the recurrence")
show(matrix([[rec_a(i,j) for i in range(8)] for j in range(8)]))

The generating function for this sequence is

This matches the terms computed from the recurrence

F = 1/(1-x-y-z)
print("The trivariate function here is")
show(F)
print("whose series expansion begins")
R = QQ[['x,y,z']]
show(1/(R(1-x-y-z) + O(R(x^4))))

The trivariate function here is

whose series expansion begins

F = 1/(1-x-y-x*y)
print("The sequence of interest is the main diagonal of")
show(F)
GFinfo2D(F)
print("so the diagonal sequence begins")
ser = F.taylor((x,0), (y,0),21).polynomial(QQ)
print([ser[k,k] for k in range(10)])
print("This matches the univariate generating function.")
f = 1/sqrt(1-6*y+y^2)
GFinfo(f, z=y)

The sequence of interest is the main diagonal of

so the diagonal sequence begins
[1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563]
This matches the univariate generating function.

C = (1 - sqrt(1-4*z))/2
print("The Catalan generating function is")
show(C)
GFinfo(C)
print("and is a root of the polynomial")
P = y^2 - y + x
show("P(x,y) = \t", P)
F = (y^2*diff(P,y)/P).subs(x=x*y)
print("This sequence is the main diagonal of the bivariate generating function")
show(F)
GFinfo2D(F)

The Catalan generating function is

and is a root of the polynomial

This sequence is the main diagonal of the bivariate generating function

N = (1 + x*(y-1) - sqrt(1 - 2*x*(y+1) + x^2*(y-1)^2) )/2
print("The Narayana generating function is")
show(N)
GFinfo2D(N)
print("and the GF is a root of the polynomial")
P = w^2 - (1+x*(y-1))*w +x*y
show("P(w,x,y) = \t", P)
F = (w^2*diff(P,w)/P).subs(x=x*w)
print("This sequence is a diagonal of the trivariate generating function")
show(F)
ser = F.taylor((x,0), (y,0), (w, 0), 26).polynomial(QQ)
print("We see that the coefficients where x and y have the same power match the initial GF")
show(matrix([[ser[i,i,j] for i in range(8)] for j in range(8)]))

The Narayana generating function is

and the GF is a root of the polynomial

This sequence is a diagonal of the trivariate generating function

We see that the coefficients where x and y have the same power match the initial GF

N = 10
f = x*sqrt(1-x-y)
F = w*x+w*x*(2*w^2+2*w)/(2+w+x+x*y)

print("Start with the generating function")
show(f)
GFinfo2D(f)
print("This can be embedded into the expansion of the trivariate function")
show(F)
ser = F.taylor((x,0), (y,0), (w, 0), 40).polynomial(QQ)
print("We see that the coefficients where x and y have the same power match the initial GF")
show(matrix([[ser[i+j,i+j,j] for i in range(8)] for j in range(8)]))

Start with the generating function

This can be embedded into the expansion of the trivariate function

We see that the coefficients where x and y have the same power match the initial GF

GFinfo(1/(1-z), exponential=True)

# First examine EGF for permutations by number of cycles
GFinfo(-log(1-z), exponential=True)

# Then do bivariate semi-exponential GF for permutations by length and number of cycles
GFinfo2D((1-z)^(-y),var1=y, var2=z,semi=True)

GFinfo(exp(z+z^2/2),exponential=True)

F = exp(y*(exp(z) - 1))
GFinfo2D(F,var1=y, var2=z,semi=True)
print("Substituting y = 1 gives the univariate EGF for set partitions")
G = F.subs(y=1)
GFinfo(G,exponential=True)

Substituting y = 1 gives the univariate EGF for set partitions

F = exp(y*z/(1-z))
GFinfo2D(F,var1=y, var2=z,semi=True)
print("Substituting y = 1 gives the univariate EGF")
G = F.subs(y=1)
GFinfo(G,exponential=True)

Substituting y = 1 gives the univariate EGF

GFinfo(exp(-z/2-z^2/4)/sqrt(1-z),exponential=True)

GFinfo(1/(2-exp(z)),exponential=True)

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

Example 2.1 - Binary Sequences Avoiding 11¶

Example 2.2 - Binomial Coefficients¶

Example 2.4 - Strings by 0s and 1s¶

Example 2.7 - Delannoy Numbers¶

Example 2.8 - no gaps of size 2¶

Example 2.9 - Binary Strings via a Transfer Matrix¶

Example 2.11 - Smirnov Words¶

Example 2.14 - Catalan Numbers¶

Example 2.15 - A Random Walk Game¶

Example 2.29 - Trivariate Binomial Diagonal¶

Example 2.33 - Delannoy Diagonal¶

Example 2.35 - Shifted Catalan as a Diagonal¶

Example 2.37 - Narayana as a Diagonal¶

Example 2.42 - Safonov Generalized Diagonal¶

Example 2.46 - Permutations EGF¶

Example 2.48 - Permutations by Number of Cycles (Stirling numbers of second kind)¶

Example 2.49 - Involutions¶

Example 2.50 - Set Partitions¶

Example 2.51 - Partitions into Ordered Sets¶

Example 2.52 - 2-Regular Graphs¶

Example 2.53 - Surjections¶