{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 4.2 (Dyck Paths and Prefixes) \n", "Computing the generating functions of Dyck Paths and Dyck Prefixes. \n", "*Requirements: None*" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-t*(x + 1/x) + 1" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Define the kernel\n", "var('x,t,Hxt,H0t')\n", "K = (1-t*(x+1/x))\n", "K" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The kernel equation is -(t*(x + 1/x) - 1)*Hxt == -H0t*t/x + 1\n" ] } ], "source": [ "# Setup the kernel equation. For ease of substitution in Sage the variables Hxt = H(x,t) and H0t = H(0,t)\n", "keq = K*Hxt == 1-t/x*H0t\n", "print(\"The kernel equation is\", keq)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\verb|The|\\phantom{\\verb!x!}\\verb|small|\\phantom{\\verb!x!}\\verb|root|\\phantom{\\verb!x!}\\verb|of|\\phantom{\\verb!x!}\\verb|the|\\phantom{\\verb!x!}\\verb|kernel|\\phantom{\\verb!x!}\\verb|is| -\\frac{\\sqrt{-4 \\, t^{2} + 1} - 1}{2 \\, t} \\phantom{\\verb!x!}\\verb|and|\\phantom{\\verb!x!}\\verb|the|\\phantom{\\verb!x!}\\verb|large|\\phantom{\\verb!x!}\\verb|root|\\phantom{\\verb!x!}\\verb|is| \\frac{\\sqrt{-4 \\, t^{2} + 1} + 1}{2 \\, t}\n", "\\end{math}" ], "text/plain": [ "'The small root of the kernel is' -1/2*(sqrt(-4*t^2 + 1) - 1)/t ' and the large root is' 1/2*(sqrt(-4*t^2 + 1) + 1)/t" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Find the large and small root of the kernel\n", "rts = [k.rhs() for k in solve(K,x)]\n", "lims = [limit(k,t=0,dir='plus') for k in rts]\n", "[r1] = [r for [l,r] in zip(lims,rts) if l==0]\n", "[R1] = [r for [l,r] in zip(lims,rts) if l==Infinity]\n", "show(\"The small root of the kernel is\", r1, \" and the large root is\", R1)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Substituting the small root gives 0 == (2*H0t*t^2 + sqrt(-4*t^2 + 1) - 1)/(sqrt(-4*t^2 + 1) - 1)\n", "This implies H(0,t) = -1/2*(sqrt(-4*t^2 + 1) - 1)/t^2\n" ] } ], "source": [ "# Substitute x = small root and solve kernel equation for H(0,t)\n", "ksubs = keq.subs(x=r1).simplify_full()\n", "print(\"Substituting the small root gives\", ksubs)\n", "h0t = ksubs.solve(H0t)[0].rhs()\n", "print(\"This implies H(0,t) = \", h0t)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Substitution of H(0,t) into the kernel equation then implies H(x,t) = -1/2*(2*t*x + sqrt(-4*t^2 + 1) - 1)/(t^2*x^2 + t^2 - t*x)\n" ] } ], "source": [ "# Back substitute H(0,t) into the kernel equation to get H(x,t)\n", "hxt = keq.subs(H0t=h0t).solve(Hxt)[0].rhs()\n", "print(\"Substitution of H(0,t) into the kernel equation then implies H(x,t) = \", hxt)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The generating function C(t) = -1/2*(2*t + sqrt(-4*t^2 + 1) - 1)/(2*t^2 - t)\n" ] } ], "source": [ "# Find the generating function C(t) = H(1,t) of Dyck prefixes\n", "C = hxt.subs(x=1)\n", "print(\"The generating function C(t) = \", C)" ] }, { "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 }