{ "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 }