{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 3.11 (Counting Leaves in Rooted Plane Trees)\n", "We compute a rational function encoding theleaves in rooted plane trees. \n", "*Requirements: None*" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The GF 1/2*(u - 1)*z - 1/2*sqrt((u^2 - 2*u + 1)*z^2 - 2*(u + 1)*z + 1) + 1/2 satisfies P(u,z,T) = 0 where P = -(u*z - z + 1)*y + y^2 + u*z\n" ] } ], "source": [ "# The bivariate generating function T(u,z) counting rooted binary trees by leaves (u) and number of vertices (z) and its algebraic equation\n", "var('u,y,z')\n", "T = 1/2*(u - 1)*z - 1/2*sqrt((u^2 - 2*u + 1)*z^2 - 2*(u + 1)*z + 1) + 1/2\n", "P = y^2 + (z-u*z-1)*y + z*u\n", "print(\"The GF {} satisfies P(u,z,T) = 0 where P = {}\".format(T,P))" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "u^3*z^4 + 3*u^2*z^4 + u^2*z^3 + u*z^4 + u*z^3 + u*z^2 + u*z" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The initial terms of T\n", "T.series(z,5).truncate().expand()" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-1" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Note T(0,0) = 0. Proposition 3.9 of the textbook applies since\n", "diff(P,y)(0,0,0)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}[u^kz^n]T(z,u) = [u^kz^ny^n] \\frac{{\\left(u y z - y z - 2 \\, y + 1\\right)} y}{u y z - u z - y z - y + 1}\n", "\\end{math}" ], "text/plain": [ "[u^kz^n]T(z,u) = [u^kz^ny^n] (u*y*z - y*z - 2*y + 1)*y/(u*y*z - u*z - y*z - y + 1)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Thus, T(u,z) as a series extraction\n", "R = (y^2*(diff(P,y)/P).subs(z=z*y)).factor()\n", "show(LatexExpr(\"[u^kz^n]T(z,u) = [u^kz^ny^n]\"),R)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "u^4*z^5 + 6*u^3*z^5 + u^3*z^4 + 6*u^2*z^5 + 3*u^2*z^4 + u*z^5 + u^2*z^3 + u*z^4 + u*z^3 + u*z^2 + u*z\n", "u^4*z^5 + 6*u^3*z^5 + u^3*z^4 + 6*u^2*z^5 + 3*u^2*z^4 + u*z^5 + u^2*z^3 + u*z^4 + u*z^3 + u*z^2 + u*z\n" ] } ], "source": [ "# Verify that the rational function series terms where z and y have the same power give T(u,z)\n", "ser = QQ[u,y,z](taylor(R,(u,0),(y,0),(z,0),20))\n", "print(add([ser[k,n,n]*u^k*z^n for k in range(6) for n in range(6)])) # Rational function coefficients\n", "print(T.series(z,6).truncate().expand()) # Bivariate generating function T" ] }, { "cell_type": "code", "execution_count": 0, "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 }