Example 3.12 (Counting Bar Graphs)

We determine a rational function encoding the generating function for edges in bar graphs.
Requirements: None

# The bivariate generating function B(u,z) counting bar graphs by horizontal edges (x) and vertical edges (y) and its algebraic equation
# NOTE: The textbook has a typo on the final term of P: it should be - x*z^2 as written here (not + x*z^2 as in the book)
var('x,y,z')
B = -1/2*(x*y + x + y + sqrt(-4*x^2*y + (x*y + x + y - 1)^2) - 1)/x
P = z - x*y - (x+y+x*y)*z - x*z^2
show("The GF B(x,y)= ", B, " satisfies P(x,y,B)=", P.subs(z=B).full_simplify())
show("where P(x,y,z)=", P)

$$\newcommand{\Bold}[1]{\mathbf{#1}}\verb|The|\phantom{\verb!x!}\verb|GF|\phantom{\verb!x!}\verb|B(x,y)=| -\frac{x y + x + y + \sqrt{-4 \, x^{2} y + {\left(x y + x + y - 1\right)}^{2}} - 1}{2 \, x} \phantom{\verb!x!}\verb|satisfies|\phantom{\verb!x!}\verb|P(x,y,B)=| 0$$

$$\newcommand{\Bold}[1]{\mathbf{#1}}\verb|where|\phantom{\verb!x!}\verb|P(x,y,z)=| -x z^{2} - x y - {\left(x y + x + y\right)} z + z$$

# The initial terms of B
taylor(B,(x,0),(y,0),5)

x^4*y + 6*x^3*y^2 + 5*x^2*y^3 + x*y^4 + x^3*y + 3*x^2*y^2 + x*y^3 + x^2*y + x*y^2 + x*y

# Note B(0,0) = 0. Proposition 3.9 of the textbook applies since
diff(P,z)(0,0,0)

1

# Thus, B(x,y) as a series extraction
R = (z^2*(diff(P,z)/P).subs(y=y*z)).factor()
show(LatexExpr("[x^iy^j]B(x,y) = [x^iy^jz^j]"),R)

$$\newcommand{\Bold}[1]{\mathbf{#1}}[x^iy^j]B(x,y) = [x^iy^jz^j] \frac{{\left(x y z + 2 \, x z + y z + x - 1\right)} z}{x y z + x y + x z + y z + x - 1}$$

# Verify that the rational function series terms where y and z have the same power give B(x,y)
ser = QQ[x,y,z](taylor(R,(x,0),(y,0),(z,0),20))
print(add([ser[k,n,n]*x^k*y^n for k in range(6) for n in range(7-k)])) # Rational function coefficients
print(taylor(B,(x,0),(y,0),6)) # Bivariate generating function B

x^5*y + 10*x^4*y^2 + 16*x^3*y^3 + 7*x^2*y^4 + x*y^5 + x^4*y + 6*x^3*y^2 + 5*x^2*y^3 + x*y^4 + x^3*y + 3*x^2*y^2 + x*y^3 + x^2*y + x*y^2 + x*y
x^5*y + 10*x^4*y^2 + 16*x^3*y^3 + 7*x^2*y^4 + x*y^5 + x^4*y + 6*x^3*y^2 + 5*x^2*y^3 + x*y^4 + x^3*y + 3*x^2*y^2 + x*y^3 + x^2*y + x*y^2 + x*y