{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Example 3.12 (Counting Bar Graphs)\n",
"We determine a rational function encoding the generating function for edges in bar graphs. \n",
"*Requirements: None*"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/latex": [
"\\begin{math}\n",
"\\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\n",
"\\end{math}"
],
"text/plain": [
"'The GF B(x,y)= ' -1/2*(x*y + x + y + sqrt(-4*x^2*y + (x*y + x + y - 1)^2) - 1)/x ' satisfies P(x,y,B)=' 0"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
""
],
"text/latex": [
"\\begin{math}\n",
"\\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\n",
"\\end{math}"
],
"text/plain": [
"'where P(x,y,z)=' -x*z^2 - x*y - (x*y + x + y)*z + z"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# The bivariate generating function B(u,z) counting bar graphs by horizontal edges (x) and vertical edges (y) and its algebraic equation\n",
"# 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)\n",
"var('x,y,z')\n",
"B = -1/2*(x*y + x + y + sqrt(-4*x^2*y + (x*y + x + y - 1)^2) - 1)/x\n",
"P = z - x*y - (x+y+x*y)*z - x*z^2\n",
"show(\"The GF B(x,y)= \", B, \" satisfies P(x,y,B)=\", P.subs(z=B).full_simplify())\n",
"show(\"where P(x,y,z)=\", P)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"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"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The initial terms of B\n",
"taylor(B,(x,0),(y,0),5)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Note B(0,0) = 0. Proposition 3.9 of the textbook applies since\n",
"diff(P,z)(0,0,0)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/latex": [
"\\begin{math}\n",
"\\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}\n",
"\\end{math}"
],
"text/plain": [
"[x^iy^j]B(x,y) = [x^iy^jz^j] (x*y*z + 2*x*z + y*z + x - 1)*z/(x*y*z + x*y + x*z + y*z + x - 1)"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Thus, B(x,y) as a series extraction\n",
"R = (z^2*(diff(P,z)/P).subs(y=y*z)).factor()\n",
"show(LatexExpr(\"[x^iy^j]B(x,y) = [x^iy^jz^j]\"),R)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"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\n",
"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\n"
]
}
],
"source": [
"# Verify that the rational function series terms where y and z have the same power give B(x,y)\n",
"ser = QQ[x,y,z](taylor(R,(x,0),(y,0),(z,0),20))\n",
"print(add([ser[k,n,n]*x^k*y^n for k in range(6) for n in range(7-k)])) # Rational function coefficients\n",
"print(taylor(B,(x,0),(y,0),6)) # Bivariate generating function B"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath 9.2",
"language": "sage",
"name": "sagemath"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}