{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 3.10 (The Catalan Generating Function as a Rational Diagonal)\n", "Expressing the Catalan generating function as the main diagonal of a rational function. \n", "*Requirements: None*" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "y^2*z - y + 1" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The Catalan generating function satisfies C(0) = 1 and is a root of\n", "var('y,z')\n", "P1 = z*y^2-y+1\n", "P1" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "y^2*z + y*(2*z - 1) + z" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The function K(z) = C(z) - 1 satisfies\n", "P2 = P1(y+1,z)\n", "P2.collect(y)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-1" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Proposition 3.8 of the textbook applies to K, since\n", "diff(P2,y)(0,0)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}K(x) = \\Delta \\frac{{\\left(2 \\, y^{2} z + 2 \\, y z - 1\\right)} y}{y^{2} z + 2 \\, y z + z - 1}\n", "\\end{math}" ], "text/plain": [ "K(x) = \\Delta (2*y^2*z + 2*y*z - 1)*y/(y^2*z + 2*y*z + z - 1)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Thus, we can express K(z) as a rational diagonal\n", "R1 = (y^2*(diff(P2,y)/P2).subs(z=z*y)).factor()\n", "show(LatexExpr(\"K(x) = \\\\Delta\"),R1)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}C(x) = \\Delta \\frac{{\\left(2 \\, y^{2} z + y z + z - 1\\right)} {\\left(y + 1\\right)}}{y^{2} z + 2 \\, y z + z - 1}\n", "\\end{math}" ], "text/plain": [ "C(x) = \\Delta (2*y^2*z + y*z + z - 1)*(y + 1)/(y^2*z + 2*y*z + z - 1)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Since, C(z) = 1 + K(z), we have the Catalan GF as a rational diagonal\n", "R2 = (R1+1).factor()\n", "show(LatexExpr(\"C(x) = \\\\Delta\"),R2)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]\n", "[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]\n" ] } ], "source": [ "# Check that the initial diagonal terms of R2 match the initial Catalan numbers\n", "ser = QQ[y,z](taylor(R2,(y,0),(z,0),20))\n", "print([ser[k,k] for k in range(10)]) # Diagonal sequence of R2\n", "\n", "GF = (1-sqrt(1-4*z))/2/z\n", "print([k for (k,j) in GF.series(z,10).coefficients()]) # Series coefficients of Catalan GF" ] }, { "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 }