
# Define the kernel
var('x,t,Hxt,H0t')
K = (1-t*(x+1/x))
K

-t*(x + 1/x) + 1


# Setup the kernel equation. For ease of substitution in Sage the variables Hxt = H(x,t) and H0t = H(0,t)
keq = K*Hxt == 1-t/x*H0t
print("The kernel equation is", keq)

The kernel equation is -(t*(x + 1/x) - 1)*Hxt == -H0t*t/x + 1


# Find the large and small root of the kernel
rts = [k.rhs() for k in solve(K,x)]
lims = [limit(k,t=0,dir='plus') for k in rts]
[r1] = [r for [l,r] in zip(lims,rts) if l==0]
[R1] = [r for [l,r] in zip(lims,rts) if l==Infinity]
show("The small root of the kernel is", r1, " and the large root is", R1)


# Substitute x = small root and solve kernel equation for H(0,t)
ksubs = keq.subs(x=r1).simplify_full()
print("Substituting the small root gives", ksubs)
h0t = ksubs.solve(H0t)[0].rhs()
print("This implies H(0,t) = ", h0t)

Substituting the small root gives 0 == (2*H0t*t^2 + sqrt(-4*t^2 + 1) - 1)/(sqrt(-4*t^2 + 1) - 1)
This implies H(0,t) =  -1/2*(sqrt(-4*t^2 + 1) - 1)/t^2


# Back substitute H(0,t) into the kernel equation to get H(x,t)
hxt = keq.subs(H0t=h0t).solve(Hxt)[0].rhs()
print("Substitution of H(0,t) into the kernel equation then implies H(x,t) = ", hxt)

Substitution of H(0,t) into the kernel equation then implies H(x,t) =  -1/2*(2*t*x + sqrt(-4*t^2 + 1) - 1)/(t^2*x^2 + t^2 - t*x)


# Find the generating function C(t) = H(1,t) of Dyck prefixes
C = hxt.subs(x=1)
print("The generating function C(t) = ", C)

The generating function C(t) =  -1/2*(2*t + sqrt(-4*t^2 + 1) - 1)/(2*t^2 - t)

Example 4.2 (Dyck Paths and Prefixes)¶