{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### This notebook contains worked examples from Chapter 2 of the text *Analytic Combinatorics in Several Variables (2nd edition)* by Pemantle, Wilson and Melczer. \n", "\n", "Further details can be found on the book website at [https://acsvproject.com/acsvbook/](https://acsvproject.com/acsvbook/) .\n", "\n", "Example numbers match the published version.\n", "\n", "**Note:** Commands involving accessing the OEIS require Sage to have access to OpenSSL, which is often not done during typical installs. Calling the OEIS is thus left as an optional parameter.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# We begin by defining some helper functions for below\n", "# MAKE SURE TO RUN THIS CELL!\n", "var('w x y z r s i j')\n", "\n", "def GFinfo(F, z=z, exponential=False, OEIS=False): \n", " if exponential==False:\n", " show(\"This generating function has the expansion\")\n", " show(F, \"=\\t\", F.series(z,10))\n", " else:\n", " pol = F.series(z,10).truncate().polynomial(QQ)\n", " terms = [[pol[k],\"\\\\frac{\" + latex(pol[k]*factorial(k)) + \"}{\" + k + \"!} \\cdot\" + latex(z^k)] for k in range(10)]\n", " nz_terms = [st for (p,st) in terms if p != 0]\n", " st = ''\n", " for k in nz_terms[0:-1]: st += k + \" + \"\n", " show(\"This exponential generating function has an expansion beginning\")\n", " show(F, \"=\\t\", st + nz_terms[-1])\n", " \n", " if OEIS==True:\n", " print(\"The OEIS has the following entry for this starting sequence\")\n", " oeis(list(F.series(z,10).truncate().polynomial(QQ)))\n", " \n", "def GFinfo2D(F, var1=x, var2=y, semi=False): \n", " if semi==False:\n", " show(\"The initial array of coefficients for this generating function is\")\n", " ser = QQ[var1,var2](F.taylor((var1,0), (var2,0), 17))\n", " show(matrix([[ser[i,j] for i in range(8)] for j in range(8)]))\n", " else:\n", " pol = QQ[var1,var2](F.taylor((var1,0), (var2,0), 21))\n", " terms = [[pol[k,n-k],\"\\\\frac{\" + latex(pol[k,n-k]*factorial(n-k)) + \"}{\" + (n-k) + \"!} \\cdot\" + latex(var1^k*var2^(n-k))] for n in range(10) for k in range(n+1)]\n", " nz_terms = [st for (p,st) in terms if p != 0]\n", " st = ''\n", " for k in nz_terms[0:-1]: st += k + \" + \"\n", " show(\"This exponential generating function has an expansion beginning\")\n", " show(F, \"=\\t\", st + nz_terms[-1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.1 - Binary Sequences Avoiding 11" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|the|\\verb| |\\verb|expansion|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|the|\\verb| |\\verb|expansion|$" ], "text/plain": [ "'This generating function has the expansion'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{1}{z^{2} + z - 1} \\verb|=\t| 1 + 1 z + 2 z^{2} + 3 z^{3} + 5 z^{4} + 8 z^{5} + 13 z^{6} + 21 z^{7} + 34 z^{8} + 55 z^{9} + \\mathcal{O}\\left(z^{10}\\right)\\)" ], "text/latex": [ "$\\displaystyle -\\frac{1}{z^{2} + z - 1} \\verb|=\t| 1 + 1 z + 2 z^{2} + 3 z^{3} + 5 z^{4} + 8 z^{5} + 13 z^{6} + 21 z^{7} + 34 z^{8} + 55 z^{9} + \\mathcal{O}\\left(z^{10}\\right)$" ], "text/plain": [ "-1/(z^2 + z - 1) '=\\t' 1 + 1*z + 2*z^2 + 3*z^3 + 5*z^4 + 8*z^5 + 13*z^6 + 21*z^7 + 34*z^8 + 55*z^9 + Order(z^10)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "GFinfo(1/(1-z-z^2))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.2 - Binomial Coefficients" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|$" ], "text/plain": [ "'The initial array of coefficients for this generating function is'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\\\\n", "1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 \\\\\n", "1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 \\\\\n", "1 & 5 & 15 & 35 & 70 & 126 & 210 & 330 \\\\\n", "1 & 6 & 21 & 56 & 126 & 252 & 462 & 792 \\\\\n", "1 & 7 & 28 & 84 & 210 & 462 & 924 & 1716 \\\\\n", "1 & 8 & 36 & 120 & 330 & 792 & 1716 & 3432\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\\\\n", "1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 \\\\\n", "1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 \\\\\n", "1 & 5 & 15 & 35 & 70 & 126 & 210 & 330 \\\\\n", "1 & 6 & 21 & 56 & 126 & 252 & 462 & 792 \\\\\n", "1 & 7 & 28 & 84 & 210 & 462 & 924 & 1716 \\\\\n", "1 & 8 & 36 & 120 & 330 & 792 & 1716 & 3432\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 1 1 1 1 1 1 1]\n", "[ 1 2 3 4 5 6 7 8]\n", "[ 1 3 6 10 15 21 28 36]\n", "[ 1 4 10 20 35 56 84 120]\n", "[ 1 5 15 35 70 126 210 330]\n", "[ 1 6 21 56 126 252 462 792]\n", "[ 1 7 28 84 210 462 924 1716]\n", "[ 1 8 36 120 330 792 1716 3432]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|equals|\\verb| |\\verb|the|\\verb| |\\verb|expected|\\verb| |\\verb|coefficients|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|equals|\\verb| |\\verb|the|\\verb| |\\verb|expected|\\verb| |\\verb|coefficients|$" ], "text/plain": [ "'This equals the expected coefficients'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\\\\n", "1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 \\\\\n", "1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 \\\\\n", "1 & 5 & 15 & 35 & 70 & 126 & 210 & 330 \\\\\n", "1 & 6 & 21 & 56 & 126 & 252 & 462 & 792 \\\\\n", "1 & 7 & 28 & 84 & 210 & 462 & 924 & 1716 \\\\\n", "1 & 8 & 36 & 120 & 330 & 792 & 1716 & 3432\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\\\\n", "1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 \\\\\n", "1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 \\\\\n", "1 & 5 & 15 & 35 & 70 & 126 & 210 & 330 \\\\\n", "1 & 6 & 21 & 56 & 126 & 252 & 462 & 792 \\\\\n", "1 & 7 & 28 & 84 & 210 & 462 & 924 & 1716 \\\\\n", "1 & 8 & 36 & 120 & 330 & 792 & 1716 & 3432\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 1 1 1 1 1 1 1]\n", "[ 1 2 3 4 5 6 7 8]\n", "[ 1 3 6 10 15 21 28 36]\n", "[ 1 4 10 20 35 56 84 120]\n", "[ 1 5 15 35 70 126 210 330]\n", "[ 1 6 21 56 126 252 462 792]\n", "[ 1 7 28 84 210 462 924 1716]\n", "[ 1 8 36 120 330 792 1716 3432]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "GFinfo2D(1/(1-x-y))\n", "show(\"This equals the expected coefficients\")\n", "show(matrix([[binomial(i+j,i) for i in range(8)] for j in range(8)]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.4 - Strings by 0s and 1s" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|$" ], "text/plain": [ "'The initial array of coefficients for this generating function is'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\\\n", "0 & 0 & 1 & 3 & 6 & 10 & 15 & 21 \\\\\n", "0 & 0 & 0 & 1 & 4 & 10 & 20 & 35 \\\\\n", "0 & 0 & 0 & 0 & 1 & 5 & 15 & 35 \\\\\n", "0 & 0 & 0 & 0 & 0 & 1 & 6 & 21 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 1 & 7 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\\\n", "0 & 0 & 1 & 3 & 6 & 10 & 15 & 21 \\\\\n", "0 & 0 & 0 & 1 & 4 & 10 & 20 & 35 \\\\\n", "0 & 0 & 0 & 0 & 1 & 5 & 15 & 35 \\\\\n", "0 & 0 & 0 & 0 & 0 & 1 & 6 & 21 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 1 & 7 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 1 1 1 1 1 1 1]\n", "[ 0 1 2 3 4 5 6 7]\n", "[ 0 0 1 3 6 10 15 21]\n", "[ 0 0 0 1 4 10 20 35]\n", "[ 0 0 0 0 1 5 15 35]\n", "[ 0 0 0 0 0 1 6 21]\n", "[ 0 0 0 0 0 0 1 7]\n", "[ 0 0 0 0 0 0 0 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "GFinfo2D(1/(1-x-x*y))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.7 - Delannoy Numbers" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|$" ], "text/plain": [ "'The initial array of coefficients for this generating function is'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 \\\\\n", "1 & 5 & 13 & 25 & 41 & 61 & 85 & 113 \\\\\n", "1 & 7 & 25 & 63 & 129 & 231 & 377 & 575 \\\\\n", "1 & 9 & 41 & 129 & 321 & 681 & 1289 & 2241 \\\\\n", "1 & 11 & 61 & 231 & 681 & 1683 & 3653 & 7183 \\\\\n", "1 & 13 & 85 & 377 & 1289 & 3653 & 8989 & 19825 \\\\\n", "1 & 15 & 113 & 575 & 2241 & 7183 & 19825 & 48639\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 \\\\\n", "1 & 5 & 13 & 25 & 41 & 61 & 85 & 113 \\\\\n", "1 & 7 & 25 & 63 & 129 & 231 & 377 & 575 \\\\\n", "1 & 9 & 41 & 129 & 321 & 681 & 1289 & 2241 \\\\\n", "1 & 11 & 61 & 231 & 681 & 1683 & 3653 & 7183 \\\\\n", "1 & 13 & 85 & 377 & 1289 & 3653 & 8989 & 19825 \\\\\n", "1 & 15 & 113 & 575 & 2241 & 7183 & 19825 & 48639\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 1 1 1 1 1 1 1]\n", "[ 1 3 5 7 9 11 13 15]\n", "[ 1 5 13 25 41 61 85 113]\n", "[ 1 7 25 63 129 231 377 575]\n", "[ 1 9 41 129 321 681 1289 2241]\n", "[ 1 11 61 231 681 1683 3653 7183]\n", "[ 1 13 85 377 1289 3653 8989 19825]\n", "[ 1 15 113 575 2241 7183 19825 48639]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "GFinfo2D(1/(1-x-y-x*y))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.8 - no gaps of size 2" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|series|\\verb| |\\verb|expansion|\\verb| |\\verb|of|\\verb| |\\verb|the|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|series|\\verb| |\\verb|expansion|\\verb| |\\verb|of|\\verb| |\\verb|the|\\verb| |\\verb|generating|\\verb| |\\verb|function|$" ], "text/plain": [ "'The series expansion of the generating function'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{x^{3} y z - x^{2} y z - x y - x z - x - 1}{w x^{4} y^{2} z^{2} - w x^{3} y^{2} z^{2} - w x^{2} y^{2} z - w x^{2} y z^{2} - w x^{2} y z - w x y z - x^{2} y z + 1}\\)" ], "text/latex": [ "$\\displaystyle -\\frac{x^{3} y z - x^{2} y z - x y - x z - x - 1}{w x^{4} y^{2} z^{2} - w x^{3} y^{2} z^{2} - w x^{2} y^{2} z - w x^{2} y z^{2} - w x^{2} y z - w x y z - x^{2} y z + 1}$" ], "text/plain": [ "-(x^3*y*z - x^2*y*z - x*y - x*z - x - 1)/(w*x^4*y^2*z^2 - w*x^3*y^2*z^2 - w*x^2*y^2*z - w*x^2*y*z^2 - w*x^2*y*z - w*x*y*z - x^2*y*z + 1)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|begins|\\verb| |\\verb|\t| w^{2} x^{2} y^{2} z^{2} + 2 \\, w x^{2} y^{2} z + 2 \\, w x^{2} y z^{2} + 2 \\, w x^{2} y z + w x y z + 2 \\, x^{2} y z + x y + x z + x + 1\\)" ], "text/latex": [ "$\\displaystyle \\verb|begins|\\verb| |\\verb|\t| w^{2} x^{2} y^{2} z^{2} + 2 \\, w x^{2} y^{2} z + 2 \\, w x^{2} y z^{2} + 2 \\, w x^{2} y z + w x y z + 2 \\, x^{2} y z + x y + x z + x + 1$" ], "text/plain": [ "'begins \\t' w^2*x^2*y^2*z^2 + 2*w*x^2*y^2*z + 2*w*x^2*y*z^2 + 2*w*x^2*y*z + w*x*y*z + 2*x^2*y*z + x*y + x*z + x + 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Build the generating function in the book\n", "var('x y z w')\n", "G1 = x*y*z*w\n", "G2 = x^2*y*z*w\n", "G3 = x*y*z*w*(x*y+x^2*y*z)/(1-x^2*y*z)\n", "G4 = x*y*z*w*(x*z+x^2*y*z)/(1-x^2*y*z)\n", "G = G1+G2+G3+G4\n", "F = (1/(1-G) - 1)/(x*y*z*w)\n", "\n", "# Find initial terms in the expansion\n", "show(\"The series expansion of the generating function\")\n", "show(F.numerator().expand()/F.denominator().expand())\n", "show(\"begins \\t\", F.taylor(x,0,2).expand())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.9 - Binary Strings via a Transfer Matrix" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The matrix containing the generating functions enumerating binary strings without consecutive 1s by starting and ending symbol is\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rr}\n", "-\\frac{1}{z^{2} + z - 1} & -\\frac{z}{z^{2} + z - 1} \\\\\n", "-\\frac{z}{z^{2} + z - 1} & \\frac{z - 1}{z^{2} + z - 1}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rr}\n", "-\\frac{1}{z^{2} + z - 1} & -\\frac{z}{z^{2} + z - 1} \\\\\n", "-\\frac{z}{z^{2} + z - 1} & \\frac{z - 1}{z^{2} + z - 1}\n", "\\end{array}\\right)$" ], "text/plain": [ "[ -1/(z^2 + z - 1) -z/(z^2 + z - 1)]\n", "[ -z/(z^2 + z - 1) (z - 1)/(z^2 + z - 1)]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "A = Matrix([[1,1],[1,0]])\n", "print(\"The matrix containing the generating functions enumerating binary strings without consecutive 1s by starting and ending symbol is\")\n", "show((matrix.identity(2) - z*A).inverse().simplify_full())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.11 - Smirnov Words " ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The generating function for Smirnov words in dimension 4 is\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{1}{\\frac{Z_{0}}{Z_{0} + 1} + \\frac{Z_{1}}{Z_{1} + 1} + \\frac{Z_{2}}{Z_{2} + 1} + \\frac{Z_{3}}{Z_{3} + 1} - 1}\\)" ], "text/latex": [ "$\\displaystyle -\\frac{1}{\\frac{Z_{0}}{Z_{0} + 1} + \\frac{Z_{1}}{Z_{1} + 1} + \\frac{Z_{2}}{Z_{2} + 1} + \\frac{Z_{3}}{Z_{3} + 1} - 1}$" ], "text/plain": [ "-1/(Z0/(Z0 + 1) + Z1/(Z1 + 1) + Z2/(Z2 + 1) + Z3/(Z3 + 1) - 1)" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "and its series expansion at the origin begins\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 1 + Z_{0} + Z_{1} + Z_{2} + Z_{3} + 2 Z_{0} Z_{1} + 2 Z_{0} Z_{2} + 2 Z_{0} Z_{3} + 2 Z_{1} Z_{2} + 2 Z_{1} Z_{3} + 2 Z_{2} Z_{3} + Z_{0}^{2} Z_{1} + Z_{0}^{2} Z_{2} + Z_{0}^{2} Z_{3} + Z_{0} Z_{1}^{2} + 6 Z_{0} Z_{1} Z_{2} + 6 Z_{0} Z_{1} Z_{3} + Z_{0} Z_{2}^{2} + 6 Z_{0} Z_{2} Z_{3} + Z_{0} Z_{3}^{2} + Z_{1}^{2} Z_{2} + Z_{1}^{2} Z_{3} + Z_{1} Z_{2}^{2} + 6 Z_{1} Z_{2} Z_{3} + Z_{1} Z_{3}^{2} + Z_{2}^{2} Z_{3} + Z_{2} Z_{3}^{2} + 2 Z_{0}^{2} Z_{1}^{2} + 6 Z_{0}^{2} Z_{1} Z_{2} + 6 Z_{0}^{2} Z_{1} Z_{3} + 2 Z_{0}^{2} Z_{2}^{2} + 6 Z_{0}^{2} Z_{2} Z_{3} + 2 Z_{0}^{2} Z_{3}^{2} + 6 Z_{0} Z_{1}^{2} Z_{2} + 6 Z_{0} Z_{1}^{2} Z_{3} + 6 Z_{0} Z_{1} Z_{2}^{2} + 24 Z_{0} Z_{1} Z_{2} Z_{3} + 6 Z_{0} Z_{1} Z_{3}^{2} + 6 Z_{0} Z_{2}^{2} Z_{3} + 6 Z_{0} Z_{2} Z_{3}^{2} + 2 Z_{1}^{2} Z_{2}^{2} + 6 Z_{1}^{2} Z_{2} Z_{3} + 2 Z_{1}^{2} Z_{3}^{2} + 6 Z_{1} Z_{2}^{2} Z_{3} + 6 Z_{1} Z_{2} Z_{3}^{2} + 2 Z_{2}^{2} Z_{3}^{2} + O(Z_{0}, Z_{1}, Z_{2}, Z_{3})^{5}\\)" ], "text/latex": [ "$\\displaystyle 1 + Z_{0} + Z_{1} + Z_{2} + Z_{3} + 2 Z_{0} Z_{1} + 2 Z_{0} Z_{2} + 2 Z_{0} Z_{3} + 2 Z_{1} Z_{2} + 2 Z_{1} Z_{3} + 2 Z_{2} Z_{3} + Z_{0}^{2} Z_{1} + Z_{0}^{2} Z_{2} + Z_{0}^{2} Z_{3} + Z_{0} Z_{1}^{2} + 6 Z_{0} Z_{1} Z_{2} + 6 Z_{0} Z_{1} Z_{3} + Z_{0} Z_{2}^{2} + 6 Z_{0} Z_{2} Z_{3} + Z_{0} Z_{3}^{2} + Z_{1}^{2} Z_{2} + Z_{1}^{2} Z_{3} + Z_{1} Z_{2}^{2} + 6 Z_{1} Z_{2} Z_{3} + Z_{1} Z_{3}^{2} + Z_{2}^{2} Z_{3} + Z_{2} Z_{3}^{2} + 2 Z_{0}^{2} Z_{1}^{2} + 6 Z_{0}^{2} Z_{1} Z_{2} + 6 Z_{0}^{2} Z_{1} Z_{3} + 2 Z_{0}^{2} Z_{2}^{2} + 6 Z_{0}^{2} Z_{2} Z_{3} + 2 Z_{0}^{2} Z_{3}^{2} + 6 Z_{0} Z_{1}^{2} Z_{2} + 6 Z_{0} Z_{1}^{2} Z_{3} + 6 Z_{0} Z_{1} Z_{2}^{2} + 24 Z_{0} Z_{1} Z_{2} Z_{3} + 6 Z_{0} Z_{1} Z_{3}^{2} + 6 Z_{0} Z_{2}^{2} Z_{3} + 6 Z_{0} Z_{2} Z_{3}^{2} + 2 Z_{1}^{2} Z_{2}^{2} + 6 Z_{1}^{2} Z_{2} Z_{3} + 2 Z_{1}^{2} Z_{3}^{2} + 6 Z_{1} Z_{2}^{2} Z_{3} + 6 Z_{1} Z_{2} Z_{3}^{2} + 2 Z_{2}^{2} Z_{3}^{2} + O(Z_{0}, Z_{1}, Z_{2}, Z_{3})^{5}$" ], "text/plain": [ "1 + Z0 + Z1 + Z2 + Z3 + 2*Z0*Z1 + 2*Z0*Z2 + 2*Z0*Z3 + 2*Z1*Z2 + 2*Z1*Z3 + 2*Z2*Z3 + Z0^2*Z1 + Z0^2*Z2 + Z0^2*Z3 + Z0*Z1^2 + 6*Z0*Z1*Z2 + 6*Z0*Z1*Z3 + Z0*Z2^2 + 6*Z0*Z2*Z3 + Z0*Z3^2 + Z1^2*Z2 + Z1^2*Z3 + Z1*Z2^2 + 6*Z1*Z2*Z3 + Z1*Z3^2 + Z2^2*Z3 + Z2*Z3^2 + 2*Z0^2*Z1^2 + 6*Z0^2*Z1*Z2 + 6*Z0^2*Z1*Z3 + 2*Z0^2*Z2^2 + 6*Z0^2*Z2*Z3 + 2*Z0^2*Z3^2 + 6*Z0*Z1^2*Z2 + 6*Z0*Z1^2*Z3 + 6*Z0*Z1*Z2^2 + 24*Z0*Z1*Z2*Z3 + 6*Z0*Z1*Z3^2 + 6*Z0*Z2^2*Z3 + 6*Z0*Z2*Z3^2 + 2*Z1^2*Z2^2 + 6*Z1^2*Z2*Z3 + 2*Z1^2*Z3^2 + 6*Z1*Z2^2*Z3 + 6*Z1*Z2*Z3^2 + 2*Z2^2*Z3^2 + O(Z0, Z1, Z2, Z3)^5" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "dim = 4\n", "Z = var('Z', n=dim)\n", "F = 1/(1-add([Z[k]/(1+Z[k]) for k in range(dim)]))\n", "print(\"The generating function for Smirnov words in dimension {} is\".format(dim))\n", "show(F)\n", "print(\"and its series expansion at the origin begins\")\n", "R = QQ[[Z]]\n", "show(R(F.numerator())/(R(F.denominator()) + O(R(Z[0]^5))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.14 - Catalan Numbers" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The Catalan generating function is\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{\\sqrt{-4 \\, z + 1} - 1}{2 \\, z}\\)" ], "text/latex": [ "$\\displaystyle -\\frac{\\sqrt{-4 \\, z + 1} - 1}{2 \\, z}$" ], "text/plain": [ "-1/2*(sqrt(-4*z + 1) - 1)/z" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|the|\\verb| |\\verb|expansion|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|the|\\verb| |\\verb|expansion|$" ], "text/plain": [ "'This generating function has the expansion'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{\\sqrt{-4 \\, z + 1} - 1}{2 \\, z} \\verb|=\t| 1 + 1 z + 2 z^{2} + 5 z^{3} + 14 z^{4} + 42 z^{5} + 132 z^{6} + 429 z^{7} + 1430 z^{8} + 4862 z^{9} + \\mathcal{O}\\left(z^{10}\\right)\\)" ], "text/latex": [ "$\\displaystyle -\\frac{\\sqrt{-4 \\, z + 1} - 1}{2 \\, z} \\verb|=\t| 1 + 1 z + 2 z^{2} + 5 z^{3} + 14 z^{4} + 42 z^{5} + 132 z^{6} + 429 z^{7} + 1430 z^{8} + 4862 z^{9} + \\mathcal{O}\\left(z^{10}\\right)$" ], "text/plain": [ "-1/2*(sqrt(-4*z + 1) - 1)/z '=\\t' 1 + 1*z + 2*z^2 + 5*z^3 + 14*z^4 + 42*z^5 + 132*z^6 + 429*z^7 + 1430*z^8 + 4862*z^9 + Order(z^10)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "C = (1 - sqrt(1-4*z))/(2*z)\n", "print(\"The Catalan generating function is\")\n", "show(C)\n", "GFinfo(C)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.15 - A Random Walk Game" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The generating function for this sequence is\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{2}{y - \\sqrt{-x + 1} - 1}\\)" ], "text/latex": [ "$\\displaystyle -\\frac{2}{y - \\sqrt{-x + 1} - 1}$" ], "text/plain": [ "-2/(y - sqrt(-x + 1) - 1)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|$" ], "text/plain": [ "'The initial array of coefficients for this generating function is'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & \\frac{1}{4} & \\frac{1}{8} & \\frac{5}{64} & \\frac{7}{128} & \\frac{21}{512} & \\frac{33}{1024} & \\frac{429}{16384} \\\\\n", "\\frac{1}{2} & \\frac{1}{4} & \\frac{5}{32} & \\frac{7}{64} & \\frac{21}{256} & \\frac{33}{512} & \\frac{429}{8192} & \\frac{715}{16384} \\\\\n", "\\frac{1}{4} & \\frac{3}{16} & \\frac{9}{64} & \\frac{7}{64} & \\frac{45}{512} & \\frac{297}{4096} & \\frac{1001}{16384} & \\frac{429}{8192} \\\\\n", "\\frac{1}{8} & \\frac{1}{8} & \\frac{7}{64} & \\frac{3}{32} & \\frac{165}{2048} & \\frac{143}{2048} & \\frac{1001}{16384} & \\frac{221}{4096} \\\\\n", "\\frac{1}{16} & \\frac{5}{64} & \\frac{5}{64} & \\frac{75}{1024} & \\frac{275}{4096} & \\frac{1001}{16384} & \\frac{455}{8192} & \\frac{3315}{65536} \\\\\n", "\\frac{1}{32} & \\frac{3}{64} & \\frac{27}{512} & \\frac{55}{1024} & \\frac{429}{8192} & \\frac{819}{16384} & \\frac{1547}{32768} & \\frac{2907}{65536} \\\\\n", "\\frac{1}{64} & \\frac{7}{256} & \\frac{35}{1024} & \\frac{77}{2048} & \\frac{637}{16384} & \\frac{637}{16384} & \\frac{2499}{65536} & \\frac{4845}{131072} \\\\\n", "\\frac{1}{128} & \\frac{1}{64} & \\frac{11}{512} & \\frac{13}{512} & \\frac{455}{16384} & \\frac{119}{4096} & \\frac{969}{32768} & \\frac{969}{32768}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & \\frac{1}{4} & \\frac{1}{8} & \\frac{5}{64} & \\frac{7}{128} & \\frac{21}{512} & \\frac{33}{1024} & \\frac{429}{16384} \\\\\n", "\\frac{1}{2} & \\frac{1}{4} & \\frac{5}{32} & \\frac{7}{64} & \\frac{21}{256} & \\frac{33}{512} & \\frac{429}{8192} & \\frac{715}{16384} \\\\\n", "\\frac{1}{4} & \\frac{3}{16} & \\frac{9}{64} & \\frac{7}{64} & \\frac{45}{512} & \\frac{297}{4096} & \\frac{1001}{16384} & \\frac{429}{8192} \\\\\n", "\\frac{1}{8} & \\frac{1}{8} & \\frac{7}{64} & \\frac{3}{32} & \\frac{165}{2048} & \\frac{143}{2048} & \\frac{1001}{16384} & \\frac{221}{4096} \\\\\n", "\\frac{1}{16} & \\frac{5}{64} & \\frac{5}{64} & \\frac{75}{1024} & \\frac{275}{4096} & \\frac{1001}{16384} & \\frac{455}{8192} & \\frac{3315}{65536} \\\\\n", "\\frac{1}{32} & \\frac{3}{64} & \\frac{27}{512} & \\frac{55}{1024} & \\frac{429}{8192} & \\frac{819}{16384} & \\frac{1547}{32768} & \\frac{2907}{65536} \\\\\n", "\\frac{1}{64} & \\frac{7}{256} & \\frac{35}{1024} & \\frac{77}{2048} & \\frac{637}{16384} & \\frac{637}{16384} & \\frac{2499}{65536} & \\frac{4845}{131072} \\\\\n", "\\frac{1}{128} & \\frac{1}{64} & \\frac{11}{512} & \\frac{13}{512} & \\frac{455}{16384} & \\frac{119}{4096} & \\frac{969}{32768} & \\frac{969}{32768}\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 1/4 1/8 5/64 7/128 21/512 33/1024 429/16384]\n", "[ 1/2 1/4 5/32 7/64 21/256 33/512 429/8192 715/16384]\n", "[ 1/4 3/16 9/64 7/64 45/512 297/4096 1001/16384 429/8192]\n", "[ 1/8 1/8 7/64 3/32 165/2048 143/2048 1001/16384 221/4096]\n", "[ 1/16 5/64 5/64 75/1024 275/4096 1001/16384 455/8192 3315/65536]\n", "[ 1/32 3/64 27/512 55/1024 429/8192 819/16384 1547/32768 2907/65536]\n", "[ 1/64 7/256 35/1024 77/2048 637/16384 637/16384 2499/65536 4845/131072]\n", "[ 1/128 1/64 11/512 13/512 455/16384 119/4096 969/32768 969/32768]" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "This matches the terms computed from the recurrence\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & \\frac{1}{4} & \\frac{1}{8} & \\frac{5}{64} & \\frac{7}{128} & \\frac{21}{512} & \\frac{33}{1024} & \\frac{429}{16384} \\\\\n", "\\frac{1}{2} & \\frac{1}{4} & \\frac{5}{32} & \\frac{7}{64} & \\frac{21}{256} & \\frac{33}{512} & \\frac{429}{8192} & \\frac{715}{16384} \\\\\n", "\\frac{1}{4} & \\frac{3}{16} & \\frac{9}{64} & \\frac{7}{64} & \\frac{45}{512} & \\frac{297}{4096} & \\frac{1001}{16384} & \\frac{429}{8192} \\\\\n", "\\frac{1}{8} & \\frac{1}{8} & \\frac{7}{64} & \\frac{3}{32} & \\frac{165}{2048} & \\frac{143}{2048} & \\frac{1001}{16384} & \\frac{221}{4096} \\\\\n", "\\frac{1}{16} & \\frac{5}{64} & \\frac{5}{64} & \\frac{75}{1024} & \\frac{275}{4096} & \\frac{1001}{16384} & \\frac{455}{8192} & \\frac{3315}{65536} \\\\\n", "\\frac{1}{32} & \\frac{3}{64} & \\frac{27}{512} & \\frac{55}{1024} & \\frac{429}{8192} & \\frac{819}{16384} & \\frac{1547}{32768} & \\frac{2907}{65536} \\\\\n", "\\frac{1}{64} & \\frac{7}{256} & \\frac{35}{1024} & \\frac{77}{2048} & \\frac{637}{16384} & \\frac{637}{16384} & \\frac{2499}{65536} & \\frac{4845}{131072} \\\\\n", "\\frac{1}{128} & \\frac{1}{64} & \\frac{11}{512} & \\frac{13}{512} & \\frac{455}{16384} & \\frac{119}{4096} & \\frac{969}{32768} & \\frac{969}{32768}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & \\frac{1}{4} & \\frac{1}{8} & \\frac{5}{64} & \\frac{7}{128} & \\frac{21}{512} & \\frac{33}{1024} & \\frac{429}{16384} \\\\\n", "\\frac{1}{2} & \\frac{1}{4} & \\frac{5}{32} & \\frac{7}{64} & \\frac{21}{256} & \\frac{33}{512} & \\frac{429}{8192} & \\frac{715}{16384} \\\\\n", "\\frac{1}{4} & \\frac{3}{16} & \\frac{9}{64} & \\frac{7}{64} & \\frac{45}{512} & \\frac{297}{4096} & \\frac{1001}{16384} & \\frac{429}{8192} \\\\\n", "\\frac{1}{8} & \\frac{1}{8} & \\frac{7}{64} & \\frac{3}{32} & \\frac{165}{2048} & \\frac{143}{2048} & \\frac{1001}{16384} & \\frac{221}{4096} \\\\\n", "\\frac{1}{16} & \\frac{5}{64} & \\frac{5}{64} & \\frac{75}{1024} & \\frac{275}{4096} & \\frac{1001}{16384} & \\frac{455}{8192} & \\frac{3315}{65536} \\\\\n", "\\frac{1}{32} & \\frac{3}{64} & \\frac{27}{512} & \\frac{55}{1024} & \\frac{429}{8192} & \\frac{819}{16384} & \\frac{1547}{32768} & \\frac{2907}{65536} \\\\\n", "\\frac{1}{64} & \\frac{7}{256} & \\frac{35}{1024} & \\frac{77}{2048} & \\frac{637}{16384} & \\frac{637}{16384} & \\frac{2499}{65536} & \\frac{4845}{131072} \\\\\n", "\\frac{1}{128} & \\frac{1}{64} & \\frac{11}{512} & \\frac{13}{512} & \\frac{455}{16384} & \\frac{119}{4096} & \\frac{969}{32768} & \\frac{969}{32768}\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 1/4 1/8 5/64 7/128 21/512 33/1024 429/16384]\n", "[ 1/2 1/4 5/32 7/64 21/256 33/512 429/8192 715/16384]\n", "[ 1/4 3/16 9/64 7/64 45/512 297/4096 1001/16384 429/8192]\n", "[ 1/8 1/8 7/64 3/32 165/2048 143/2048 1001/16384 221/4096]\n", "[ 1/16 5/64 5/64 75/1024 275/4096 1001/16384 455/8192 3315/65536]\n", "[ 1/32 3/64 27/512 55/1024 429/8192 819/16384 1547/32768 2907/65536]\n", "[ 1/64 7/256 35/1024 77/2048 637/16384 637/16384 2499/65536 4845/131072]\n", "[ 1/128 1/64 11/512 13/512 455/16384 119/4096 969/32768 969/32768]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "F = 2/(1+sqrt(1-x)-y)\n", "print(\"The generating function for this sequence is\")\n", "show(F)\n", "GFinfo2D(F)\n", "\n", "# Compute starting terms in sequence using recursion \n", "@cached_function\n", "def rec_a(r,s):\n", " if (r<0 or s<0):\n", " return 0\n", " elif (r==0 and s==0):\n", " return 1\n", " else:\n", " return (rec_a(r,s-1) + rec_a(r-1,s+1))/2\n", "\n", "print(\"This matches the terms computed from the recurrence\")\n", "show(matrix([[rec_a(i,j) for i in range(8)] for j in range(8)]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.29 - Trivariate Binomial Diagonal" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The trivariate function here is\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{1}{x + y + z - 1}\\)" ], "text/latex": [ "$\\displaystyle -\\frac{1}{x + y + z - 1}$" ], "text/plain": [ "-1/(x + y + z - 1)" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "whose series expansion begins\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle 1 + x + y + z + x^{2} + 2 x y + 2 x z + y^{2} + 2 y z + z^{2} + x^{3} + 3 x^{2} y + 3 x^{2} z + 3 x y^{2} + 6 x y z + 3 x z^{2} + y^{3} + 3 y^{2} z + 3 y z^{2} + z^{3} + O(x, y, z)^{4}\\)" ], "text/latex": [ "$\\displaystyle 1 + x + y + z + x^{2} + 2 x y + 2 x z + y^{2} + 2 y z + z^{2} + x^{3} + 3 x^{2} y + 3 x^{2} z + 3 x y^{2} + 6 x y z + 3 x z^{2} + y^{3} + 3 y^{2} z + 3 y z^{2} + z^{3} + O(x, y, z)^{4}$" ], "text/plain": [ "1 + x + y + z + x^2 + 2*x*y + 2*x*z + y^2 + 2*y*z + z^2 + x^3 + 3*x^2*y + 3*x^2*z + 3*x*y^2 + 6*x*y*z + 3*x*z^2 + y^3 + 3*y^2*z + 3*y*z^2 + z^3 + O(x, y, z)^4" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "F = 1/(1-x-y-z)\n", "print(\"The trivariate function here is\")\n", "show(F)\n", "print(\"whose series expansion begins\")\n", "R = QQ[['x,y,z']]\n", "show(1/(R(1-x-y-z) + O(R(x^4))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.33 - Delannoy Diagonal" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The sequence of interest is the main diagonal of\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{1}{x y + x + y - 1}\\)" ], "text/latex": [ "$\\displaystyle -\\frac{1}{x y + x + y - 1}$" ], "text/plain": [ "-1/(x*y + x + y - 1)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|$" ], "text/plain": [ "'The initial array of coefficients for this generating function is'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 \\\\\n", "1 & 5 & 13 & 25 & 41 & 61 & 85 & 113 \\\\\n", "1 & 7 & 25 & 63 & 129 & 231 & 377 & 575 \\\\\n", "1 & 9 & 41 & 129 & 321 & 681 & 1289 & 2241 \\\\\n", "1 & 11 & 61 & 231 & 681 & 1683 & 3653 & 7183 \\\\\n", "1 & 13 & 85 & 377 & 1289 & 3653 & 8989 & 19825 \\\\\n", "1 & 15 & 113 & 575 & 2241 & 7183 & 19825 & 48639\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 \\\\\n", "1 & 5 & 13 & 25 & 41 & 61 & 85 & 113 \\\\\n", "1 & 7 & 25 & 63 & 129 & 231 & 377 & 575 \\\\\n", "1 & 9 & 41 & 129 & 321 & 681 & 1289 & 2241 \\\\\n", "1 & 11 & 61 & 231 & 681 & 1683 & 3653 & 7183 \\\\\n", "1 & 13 & 85 & 377 & 1289 & 3653 & 8989 & 19825 \\\\\n", "1 & 15 & 113 & 575 & 2241 & 7183 & 19825 & 48639\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 1 1 1 1 1 1 1]\n", "[ 1 3 5 7 9 11 13 15]\n", "[ 1 5 13 25 41 61 85 113]\n", "[ 1 7 25 63 129 231 377 575]\n", "[ 1 9 41 129 321 681 1289 2241]\n", "[ 1 11 61 231 681 1683 3653 7183]\n", "[ 1 13 85 377 1289 3653 8989 19825]\n", "[ 1 15 113 575 2241 7183 19825 48639]" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "so the diagonal sequence begins\n", "[1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563]\n", "This matches the univariate generating function.\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|the|\\verb| |\\verb|expansion|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|the|\\verb| |\\verb|expansion|$" ], "text/plain": [ "'This generating function has the expansion'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\frac{1}{\\sqrt{y^{2} - 6 \\, y + 1}} \\verb|=\t| 1 + 3 y + 13 y^{2} + 63 y^{3} + 321 y^{4} + 1683 y^{5} + 8989 y^{6} + 48639 y^{7} + 265729 y^{8} + 1462563 y^{9} + \\mathcal{O}\\left(y^{10}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\frac{1}{\\sqrt{y^{2} - 6 \\, y + 1}} \\verb|=\t| 1 + 3 y + 13 y^{2} + 63 y^{3} + 321 y^{4} + 1683 y^{5} + 8989 y^{6} + 48639 y^{7} + 265729 y^{8} + 1462563 y^{9} + \\mathcal{O}\\left(y^{10}\\right)$" ], "text/plain": [ "1/sqrt(y^2 - 6*y + 1) '=\\t' 1 + 3*y + 13*y^2 + 63*y^3 + 321*y^4 + 1683*y^5 + 8989*y^6 + 48639*y^7 + 265729*y^8 + 1462563*y^9 + Order(y^10)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "F = 1/(1-x-y-x*y)\n", "print(\"The sequence of interest is the main diagonal of\")\n", "show(F)\n", "GFinfo2D(F)\n", "print(\"so the diagonal sequence begins\")\n", "ser = F.taylor((x,0), (y,0),21).polynomial(QQ)\n", "print([ser[k,k] for k in range(10)])\n", "print(\"This matches the univariate generating function.\")\n", "f = 1/sqrt(1-6*y+y^2)\n", "GFinfo(f, z=y)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.35 - Shifted Catalan as a Diagonal" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The Catalan generating function is\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{1}{2} \\, \\sqrt{-4 \\, z + 1} + \\frac{1}{2}\\)" ], "text/latex": [ "$\\displaystyle -\\frac{1}{2} \\, \\sqrt{-4 \\, z + 1} + \\frac{1}{2}$" ], "text/plain": [ "-1/2*sqrt(-4*z + 1) + 1/2" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|the|\\verb| |\\verb|expansion|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|the|\\verb| |\\verb|expansion|$" ], "text/plain": [ "'This generating function has the expansion'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{1}{2} \\, \\sqrt{-4 \\, z + 1} + \\frac{1}{2} \\verb|=\t| 1 z + 1 z^{2} + 2 z^{3} + 5 z^{4} + 14 z^{5} + 42 z^{6} + 132 z^{7} + 429 z^{8} + 1430 z^{9} + \\mathcal{O}\\left(z^{10}\\right)\\)" ], "text/latex": [ "$\\displaystyle -\\frac{1}{2} \\, \\sqrt{-4 \\, z + 1} + \\frac{1}{2} \\verb|=\t| 1 z + 1 z^{2} + 2 z^{3} + 5 z^{4} + 14 z^{5} + 42 z^{6} + 132 z^{7} + 429 z^{8} + 1430 z^{9} + \\mathcal{O}\\left(z^{10}\\right)$" ], "text/plain": [ "-1/2*sqrt(-4*z + 1) + 1/2 '=\\t' 1*z + 1*z^2 + 2*z^3 + 5*z^4 + 14*z^5 + 42*z^6 + 132*z^7 + 429*z^8 + 1430*z^9 + Order(z^10)" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "and is a root of the polynomial\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|P(x,y)|\\verb| |\\verb|=|\\verb| |\\verb|\t| y^{2} + x - y\\)" ], "text/latex": [ "$\\displaystyle \\verb|P(x,y)|\\verb| |\\verb|=|\\verb| |\\verb|\t| y^{2} + x - y$" ], "text/plain": [ "'P(x,y) = \\t' y^2 + x - y" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "This sequence is the main diagonal of the bivariate generating function\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\frac{{\\left(2 \\, y - 1\\right)} y^{2}}{x y + y^{2} - y}\\)" ], "text/latex": [ "$\\displaystyle \\frac{{\\left(2 \\, y - 1\\right)} y^{2}}{x y + y^{2} - y}$" ], "text/plain": [ "(2*y - 1)*y^2/(x*y + y^2 - y)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|$" ], "text/plain": [ "'The initial array of coefficients for this generating function is'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "-1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\\\n", "-1 & -1 & 0 & 2 & 5 & 9 & 14 & 20 \\\\\n", "-1 & -2 & -2 & 0 & 5 & 14 & 28 & 48 \\\\\n", "-1 & -3 & -5 & -5 & 0 & 14 & 42 & 90 \\\\\n", "-1 & -4 & -9 & -14 & -14 & 0 & 42 & 132 \\\\\n", "-1 & -5 & -14 & -28 & -42 & -42 & 0 & 132\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "-1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\\\n", "-1 & -1 & 0 & 2 & 5 & 9 & 14 & 20 \\\\\n", "-1 & -2 & -2 & 0 & 5 & 14 & 28 & 48 \\\\\n", "-1 & -3 & -5 & -5 & 0 & 14 & 42 & 90 \\\\\n", "-1 & -4 & -9 & -14 & -14 & 0 & 42 & 132 \\\\\n", "-1 & -5 & -14 & -28 & -42 & -42 & 0 & 132\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 0 0 0 0 0 0 0 0]\n", "[ 1 1 1 1 1 1 1 1]\n", "[ -1 0 1 2 3 4 5 6]\n", "[ -1 -1 0 2 5 9 14 20]\n", "[ -1 -2 -2 0 5 14 28 48]\n", "[ -1 -3 -5 -5 0 14 42 90]\n", "[ -1 -4 -9 -14 -14 0 42 132]\n", "[ -1 -5 -14 -28 -42 -42 0 132]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "C = (1 - sqrt(1-4*z))/2\n", "print(\"The Catalan generating function is\")\n", "show(C)\n", "GFinfo(C)\n", "print(\"and is a root of the polynomial\")\n", "P = y^2 - y + x\n", "show(\"P(x,y) = \\t\", P)\n", "F = (y^2*diff(P,y)/P).subs(x=x*y)\n", "print(\"This sequence is the main diagonal of the bivariate generating function\")\n", "show(F)\n", "GFinfo2D(F)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.37 - Narayana as a Diagonal" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The Narayana generating function is\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\frac{1}{2} \\, x {\\left(y - 1\\right)} - \\frac{1}{2} \\, \\sqrt{x^{2} {\\left(y - 1\\right)}^{2} - 2 \\, x {\\left(y + 1\\right)} + 1} + \\frac{1}{2}\\)" ], "text/latex": [ "$\\displaystyle \\frac{1}{2} \\, x {\\left(y - 1\\right)} - \\frac{1}{2} \\, \\sqrt{x^{2} {\\left(y - 1\\right)}^{2} - 2 \\, x {\\left(y + 1\\right)} + 1} + \\frac{1}{2}$" ], "text/plain": [ "1/2*x*(y - 1) - 1/2*sqrt(x^2*(y - 1)^2 - 2*x*(y + 1) + 1) + 1/2" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|$" ], "text/plain": [ "'The initial array of coefficients for this generating function is'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n", "0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "0 & 0 & 0 & 1 & 3 & 6 & 10 & 15 \\\\\n", "0 & 0 & 0 & 0 & 1 & 6 & 20 & 50 \\\\\n", "0 & 0 & 0 & 0 & 0 & 1 & 10 & 50 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 1 & 15 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n", "0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "0 & 0 & 0 & 1 & 3 & 6 & 10 & 15 \\\\\n", "0 & 0 & 0 & 0 & 1 & 6 & 20 & 50 \\\\\n", "0 & 0 & 0 & 0 & 0 & 1 & 10 & 50 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 1 & 15 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 0 0 0 0 0 0 0 0]\n", "[ 0 1 1 1 1 1 1 1]\n", "[ 0 0 0 1 3 6 10 15]\n", "[ 0 0 0 0 1 6 20 50]\n", "[ 0 0 0 0 0 1 10 50]\n", "[ 0 0 0 0 0 0 1 15]\n", "[ 0 0 0 0 0 0 0 1]\n", "[ 0 0 0 0 0 0 0 0]" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "and the GF is a root of the polynomial\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|P(w,x,y)|\\verb| |\\verb|=|\\verb| |\\verb|\t| -{\\left(x {\\left(y - 1\\right)} + 1\\right)} w + w^{2} + x y\\)" ], "text/latex": [ "$\\displaystyle \\verb|P(w,x,y)|\\verb| |\\verb|=|\\verb| |\\verb|\t| -{\\left(x {\\left(y - 1\\right)} + 1\\right)} w + w^{2} + x y$" ], "text/plain": [ "'P(w,x,y) = \\t' -(x*(y - 1) + 1)*w + w^2 + x*y" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "This sequence is a diagonal of the trivariate generating function\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{{\\left(w x {\\left(y - 1\\right)} - 2 \\, w + 1\\right)} w^{2}}{w x y - {\\left(w x {\\left(y - 1\\right)} + 1\\right)} w + w^{2}}\\)" ], "text/latex": [ "$\\displaystyle -\\frac{{\\left(w x {\\left(y - 1\\right)} - 2 \\, w + 1\\right)} w^{2}}{w x y - {\\left(w x {\\left(y - 1\\right)} + 1\\right)} w + w^{2}}$" ], "text/plain": [ "-(w*x*(y - 1) - 2*w + 1)*w^2/(w*x*y - (w*x*(y - 1) + 1)*w + w^2)" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "We see that the coefficients where x and y have the same power match the initial GF\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n", "0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "0 & 0 & 0 & 1 & 3 & 6 & 10 & 15 \\\\\n", "0 & 0 & 0 & 0 & 1 & 6 & 20 & 50 \\\\\n", "0 & 0 & 0 & 0 & 0 & 1 & 10 & 50 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 1 & 15 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n", "0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\\n", "0 & 0 & 0 & 1 & 3 & 6 & 10 & 15 \\\\\n", "0 & 0 & 0 & 0 & 1 & 6 & 20 & 50 \\\\\n", "0 & 0 & 0 & 0 & 0 & 1 & 10 & 50 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 1 & 15 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 0 0 0 0 0 0 0 0]\n", "[ 0 1 1 1 1 1 1 1]\n", "[ 0 0 0 1 3 6 10 15]\n", "[ 0 0 0 0 1 6 20 50]\n", "[ 0 0 0 0 0 1 10 50]\n", "[ 0 0 0 0 0 0 1 15]\n", "[ 0 0 0 0 0 0 0 1]\n", "[ 0 0 0 0 0 0 0 0]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "N = (1 + x*(y-1) - sqrt(1 - 2*x*(y+1) + x^2*(y-1)^2) )/2\n", "print(\"The Narayana generating function is\")\n", "show(N)\n", "GFinfo2D(N)\n", "print(\"and the GF is a root of the polynomial\")\n", "P = w^2 - (1+x*(y-1))*w +x*y\n", "show(\"P(w,x,y) = \\t\", P)\n", "F = (w^2*diff(P,w)/P).subs(x=x*w)\n", "print(\"This sequence is a diagonal of the trivariate generating function\")\n", "show(F)\n", "ser = F.taylor((x,0), (y,0), (w, 0), 26).polynomial(QQ)\n", "print(\"We see that the coefficients where x and y have the same power match the initial GF\")\n", "show(matrix([[ser[i,i,j] for i in range(8)] for j in range(8)]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.42 - Safonov Generalized Diagonal" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Start with the generating function\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle x \\sqrt{-x - y + 1}\\)" ], "text/latex": [ "$\\displaystyle x \\sqrt{-x - y + 1}$" ], "text/plain": [ "x*sqrt(-x - y + 1)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|\\)" ], "text/latex": [ "$\\displaystyle \\verb|The|\\verb| |\\verb|initial|\\verb| |\\verb|array|\\verb| |\\verb|of|\\verb| |\\verb|coefficients|\\verb| |\\verb|for|\\verb| |\\verb|this|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|is|$" ], "text/plain": [ "'The initial array of coefficients for this generating function is'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "0 & 1 & -\\frac{1}{2} & -\\frac{1}{8} & -\\frac{1}{16} & -\\frac{5}{128} & -\\frac{7}{256} & -\\frac{21}{1024} \\\\\n", "0 & -\\frac{1}{2} & -\\frac{1}{4} & -\\frac{3}{16} & -\\frac{5}{32} & -\\frac{35}{256} & -\\frac{63}{512} & -\\frac{231}{2048} \\\\\n", "0 & -\\frac{1}{8} & -\\frac{3}{16} & -\\frac{15}{64} & -\\frac{35}{128} & -\\frac{315}{1024} & -\\frac{693}{2048} & -\\frac{3003}{8192} \\\\\n", "0 & -\\frac{1}{16} & -\\frac{5}{32} & -\\frac{35}{128} & -\\frac{105}{256} & -\\frac{1155}{2048} & -\\frac{3003}{4096} & -\\frac{15015}{16384} \\\\\n", "0 & -\\frac{5}{128} & -\\frac{35}{256} & -\\frac{315}{1024} & -\\frac{1155}{2048} & -\\frac{15015}{16384} & -\\frac{45045}{32768} & -\\frac{255255}{131072} \\\\\n", "0 & -\\frac{7}{256} & -\\frac{63}{512} & -\\frac{693}{2048} & -\\frac{3003}{4096} & -\\frac{45045}{32768} & -\\frac{153153}{65536} & -\\frac{969969}{262144} \\\\\n", "0 & -\\frac{21}{1024} & -\\frac{231}{2048} & -\\frac{3003}{8192} & -\\frac{15015}{16384} & -\\frac{255255}{131072} & -\\frac{969969}{262144} & -\\frac{6789783}{1048576} \\\\\n", "0 & -\\frac{33}{2048} & -\\frac{429}{4096} & -\\frac{6435}{16384} & -\\frac{36465}{32768} & -\\frac{692835}{262144} & -\\frac{2909907}{524288} & -\\frac{22309287}{2097152}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "0 & 1 & -\\frac{1}{2} & -\\frac{1}{8} & -\\frac{1}{16} & -\\frac{5}{128} & -\\frac{7}{256} & -\\frac{21}{1024} \\\\\n", "0 & -\\frac{1}{2} & -\\frac{1}{4} & -\\frac{3}{16} & -\\frac{5}{32} & -\\frac{35}{256} & -\\frac{63}{512} & -\\frac{231}{2048} \\\\\n", "0 & -\\frac{1}{8} & -\\frac{3}{16} & -\\frac{15}{64} & -\\frac{35}{128} & -\\frac{315}{1024} & -\\frac{693}{2048} & -\\frac{3003}{8192} \\\\\n", "0 & -\\frac{1}{16} & -\\frac{5}{32} & -\\frac{35}{128} & -\\frac{105}{256} & -\\frac{1155}{2048} & -\\frac{3003}{4096} & -\\frac{15015}{16384} \\\\\n", "0 & -\\frac{5}{128} & -\\frac{35}{256} & -\\frac{315}{1024} & -\\frac{1155}{2048} & -\\frac{15015}{16384} & -\\frac{45045}{32768} & -\\frac{255255}{131072} \\\\\n", "0 & -\\frac{7}{256} & -\\frac{63}{512} & -\\frac{693}{2048} & -\\frac{3003}{4096} & -\\frac{45045}{32768} & -\\frac{153153}{65536} & -\\frac{969969}{262144} \\\\\n", "0 & -\\frac{21}{1024} & -\\frac{231}{2048} & -\\frac{3003}{8192} & -\\frac{15015}{16384} & -\\frac{255255}{131072} & -\\frac{969969}{262144} & -\\frac{6789783}{1048576} \\\\\n", "0 & -\\frac{33}{2048} & -\\frac{429}{4096} & -\\frac{6435}{16384} & -\\frac{36465}{32768} & -\\frac{692835}{262144} & -\\frac{2909907}{524288} & -\\frac{22309287}{2097152}\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 0 1 -1/2 -1/8 -1/16 -5/128 -7/256 -21/1024]\n", "[ 0 -1/2 -1/4 -3/16 -5/32 -35/256 -63/512 -231/2048]\n", "[ 0 -1/8 -3/16 -15/64 -35/128 -315/1024 -693/2048 -3003/8192]\n", "[ 0 -1/16 -5/32 -35/128 -105/256 -1155/2048 -3003/4096 -15015/16384]\n", "[ 0 -5/128 -35/256 -315/1024 -1155/2048 -15015/16384 -45045/32768 -255255/131072]\n", "[ 0 -7/256 -63/512 -693/2048 -3003/4096 -45045/32768 -153153/65536 -969969/262144]\n", "[ 0 -21/1024 -231/2048 -3003/8192 -15015/16384 -255255/131072 -969969/262144 -6789783/1048576]\n", "[ 0 -33/2048 -429/4096 -6435/16384 -36465/32768 -692835/262144 -2909907/524288 -22309287/2097152]" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "This can be embedded into the expansion of the trivariate function\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\frac{2 \\, {\\left(w^{2} + w\\right)} w x}{x y + w + x + 2} + w x\\)" ], "text/latex": [ "$\\displaystyle \\frac{2 \\, {\\left(w^{2} + w\\right)} w x}{x y + w + x + 2} + w x$" ], "text/plain": [ "2*(w^2 + w)*w*x/(x*y + w + x + 2) + w*x" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "We see that the coefficients where x and y have the same power match the initial GF\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "0 & 1 & -\\frac{1}{2} & -\\frac{1}{8} & -\\frac{1}{16} & -\\frac{5}{128} & -\\frac{7}{256} & -\\frac{21}{1024} \\\\\n", "0 & -\\frac{1}{2} & -\\frac{1}{4} & -\\frac{3}{16} & -\\frac{5}{32} & -\\frac{35}{256} & -\\frac{63}{512} & -\\frac{231}{2048} \\\\\n", "0 & -\\frac{1}{8} & -\\frac{3}{16} & -\\frac{15}{64} & -\\frac{35}{128} & -\\frac{315}{1024} & -\\frac{693}{2048} & -\\frac{3003}{8192} \\\\\n", "0 & -\\frac{1}{16} & -\\frac{5}{32} & -\\frac{35}{128} & -\\frac{105}{256} & -\\frac{1155}{2048} & -\\frac{3003}{4096} & -\\frac{15015}{16384} \\\\\n", "0 & -\\frac{5}{128} & -\\frac{35}{256} & -\\frac{315}{1024} & -\\frac{1155}{2048} & -\\frac{15015}{16384} & -\\frac{45045}{32768} & -\\frac{255255}{131072} \\\\\n", "0 & -\\frac{7}{256} & -\\frac{63}{512} & -\\frac{693}{2048} & -\\frac{3003}{4096} & -\\frac{45045}{32768} & -\\frac{153153}{65536} & -\\frac{969969}{262144} \\\\\n", "0 & -\\frac{21}{1024} & -\\frac{231}{2048} & -\\frac{3003}{8192} & -\\frac{15015}{16384} & -\\frac{255255}{131072} & -\\frac{969969}{262144} & -\\frac{6789783}{1048576} \\\\\n", "0 & -\\frac{33}{2048} & -\\frac{429}{4096} & -\\frac{6435}{16384} & -\\frac{36465}{32768} & -\\frac{692835}{262144} & -\\frac{2909907}{524288} & -\\frac{22309287}{2097152}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrrrr}\n", "0 & 1 & -\\frac{1}{2} & -\\frac{1}{8} & -\\frac{1}{16} & -\\frac{5}{128} & -\\frac{7}{256} & -\\frac{21}{1024} \\\\\n", "0 & -\\frac{1}{2} & -\\frac{1}{4} & -\\frac{3}{16} & -\\frac{5}{32} & -\\frac{35}{256} & -\\frac{63}{512} & -\\frac{231}{2048} \\\\\n", "0 & -\\frac{1}{8} & -\\frac{3}{16} & -\\frac{15}{64} & -\\frac{35}{128} & -\\frac{315}{1024} & -\\frac{693}{2048} & -\\frac{3003}{8192} \\\\\n", "0 & -\\frac{1}{16} & -\\frac{5}{32} & -\\frac{35}{128} & -\\frac{105}{256} & -\\frac{1155}{2048} & -\\frac{3003}{4096} & -\\frac{15015}{16384} \\\\\n", "0 & -\\frac{5}{128} & -\\frac{35}{256} & -\\frac{315}{1024} & -\\frac{1155}{2048} & -\\frac{15015}{16384} & -\\frac{45045}{32768} & -\\frac{255255}{131072} \\\\\n", "0 & -\\frac{7}{256} & -\\frac{63}{512} & -\\frac{693}{2048} & -\\frac{3003}{4096} & -\\frac{45045}{32768} & -\\frac{153153}{65536} & -\\frac{969969}{262144} \\\\\n", "0 & -\\frac{21}{1024} & -\\frac{231}{2048} & -\\frac{3003}{8192} & -\\frac{15015}{16384} & -\\frac{255255}{131072} & -\\frac{969969}{262144} & -\\frac{6789783}{1048576} \\\\\n", "0 & -\\frac{33}{2048} & -\\frac{429}{4096} & -\\frac{6435}{16384} & -\\frac{36465}{32768} & -\\frac{692835}{262144} & -\\frac{2909907}{524288} & -\\frac{22309287}{2097152}\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 0 1 -1/2 -1/8 -1/16 -5/128 -7/256 -21/1024]\n", "[ 0 -1/2 -1/4 -3/16 -5/32 -35/256 -63/512 -231/2048]\n", "[ 0 -1/8 -3/16 -15/64 -35/128 -315/1024 -693/2048 -3003/8192]\n", "[ 0 -1/16 -5/32 -35/128 -105/256 -1155/2048 -3003/4096 -15015/16384]\n", "[ 0 -5/128 -35/256 -315/1024 -1155/2048 -15015/16384 -45045/32768 -255255/131072]\n", "[ 0 -7/256 -63/512 -693/2048 -3003/4096 -45045/32768 -153153/65536 -969969/262144]\n", "[ 0 -21/1024 -231/2048 -3003/8192 -15015/16384 -255255/131072 -969969/262144 -6789783/1048576]\n", "[ 0 -33/2048 -429/4096 -6435/16384 -36465/32768 -692835/262144 -2909907/524288 -22309287/2097152]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "N = 10\n", "f = x*sqrt(1-x-y)\n", "F = w*x+w*x*(2*w^2+2*w)/(2+w+x+x*y)\n", "\n", "print(\"Start with the generating function\")\n", "show(f)\n", "GFinfo2D(f)\n", "print(\"This can be embedded into the expansion of the trivariate function\")\n", "show(F)\n", "ser = F.taylor((x,0), (y,0), (w, 0), 40).polynomial(QQ)\n", "print(\"We see that the coefficients where x and y have the same power match the initial GF\")\n", "show(matrix([[ser[i+j,i+j,j] for i in range(8)] for j in range(8)]))\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.46 - Permutations EGF" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|$" ], "text/plain": [ "'This exponential generating function has an expansion beginning'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{1}{z - 1} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 2 }{ 2 !} \\cdot z^{2} + \\frac{ 6 }{ 3 !} \\cdot z^{3} + \\frac{ 24 }{ 4 !} \\cdot z^{4} + \\frac{ 120 }{ 5 !} \\cdot z^{5} + \\frac{ 720 }{ 6 !} \\cdot z^{6} + \\frac{ 5040 }{ 7 !} \\cdot z^{7} + \\frac{ 40320 }{ 8 !} \\cdot z^{8} + \\frac{ 362880 }{ 9 !} \\cdot z^{9}\\)" ], "text/latex": [ "$\\displaystyle -\\frac{1}{z - 1} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 2 }{ 2 !} \\cdot z^{2} + \\frac{ 6 }{ 3 !} \\cdot z^{3} + \\frac{ 24 }{ 4 !} \\cdot z^{4} + \\frac{ 120 }{ 5 !} \\cdot z^{5} + \\frac{ 720 }{ 6 !} \\cdot z^{6} + \\frac{ 5040 }{ 7 !} \\cdot z^{7} + \\frac{ 40320 }{ 8 !} \\cdot z^{8} + \\frac{ 362880 }{ 9 !} \\cdot z^{9}$" ], "text/plain": [ "-1/(z - 1) '=\\t' \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 2 }{ 2 !} \\cdot z^{2} + \\frac{ 6 }{ 3 !} \\cdot z^{3} + \\frac{ 24 }{ 4 !} \\cdot z^{4} + \\frac{ 120 }{ 5 !} \\cdot z^{5} + \\frac{ 720 }{ 6 !} \\cdot z^{6} + \\frac{ 5040 }{ 7 !} \\cdot z^{7} + \\frac{ 40320 }{ 8 !} \\cdot z^{8} + \\frac{ 362880 }{ 9 !} \\cdot z^{9}" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "GFinfo(1/(1-z), exponential=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.48 - Permutations by Number of Cycles (Stirling numbers of second kind)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|$" ], "text/plain": [ "'This exponential generating function has an expansion beginning'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle -\\log\\left(-z + 1\\right) \\verb|=\t| \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 1 }{ 2 !} \\cdot z^{2} + \\frac{ 2 }{ 3 !} \\cdot z^{3} + \\frac{ 6 }{ 4 !} \\cdot z^{4} + \\frac{ 24 }{ 5 !} \\cdot z^{5} + \\frac{ 120 }{ 6 !} \\cdot z^{6} + \\frac{ 720 }{ 7 !} \\cdot z^{7} + \\frac{ 5040 }{ 8 !} \\cdot z^{8} + \\frac{ 40320 }{ 9 !} \\cdot z^{9}\\)" ], "text/latex": [ "$\\displaystyle -\\log\\left(-z + 1\\right) \\verb|=\t| \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 1 }{ 2 !} \\cdot z^{2} + \\frac{ 2 }{ 3 !} \\cdot z^{3} + \\frac{ 6 }{ 4 !} \\cdot z^{4} + \\frac{ 24 }{ 5 !} \\cdot z^{5} + \\frac{ 120 }{ 6 !} \\cdot z^{6} + \\frac{ 720 }{ 7 !} \\cdot z^{7} + \\frac{ 5040 }{ 8 !} \\cdot z^{8} + \\frac{ 40320 }{ 9 !} \\cdot z^{9}$" ], "text/plain": [ "-log(-z + 1) '=\\t' \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 1 }{ 2 !} \\cdot z^{2} + \\frac{ 2 }{ 3 !} \\cdot z^{3} + \\frac{ 6 }{ 4 !} \\cdot z^{4} + \\frac{ 24 }{ 5 !} \\cdot z^{5} + \\frac{ 120 }{ 6 !} \\cdot z^{6} + \\frac{ 720 }{ 7 !} \\cdot z^{7} + \\frac{ 5040 }{ 8 !} \\cdot z^{8} + \\frac{ 40320 }{ 9 !} \\cdot z^{9}" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|$" ], "text/plain": [ "'This exponential generating function has an expansion beginning'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\frac{1}{{\\left(-z + 1\\right)}^{y}} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot y z + \\frac{ 1 }{ 2 !} \\cdot y z^{2} + \\frac{ 2 }{ 3 !} \\cdot y z^{3} + \\frac{ 1 }{ 2 !} \\cdot y^{2} z^{2} + \\frac{ 6 }{ 4 !} \\cdot y z^{4} + \\frac{ 3 }{ 3 !} \\cdot y^{2} z^{3} + \\frac{ 24 }{ 5 !} \\cdot y z^{5} + \\frac{ 11 }{ 4 !} \\cdot y^{2} z^{4} + \\frac{ 1 }{ 3 !} \\cdot y^{3} z^{3} + \\frac{ 120 }{ 6 !} \\cdot y z^{6} + \\frac{ 50 }{ 5 !} \\cdot y^{2} z^{5} + \\frac{ 6 }{ 4 !} \\cdot y^{3} z^{4} + \\frac{ 720 }{ 7 !} \\cdot y z^{7} + \\frac{ 274 }{ 6 !} \\cdot y^{2} z^{6} + \\frac{ 35 }{ 5 !} \\cdot y^{3} z^{5} + \\frac{ 1 }{ 4 !} \\cdot y^{4} z^{4} + \\frac{ 5040 }{ 8 !} \\cdot y z^{8} + \\frac{ 1764 }{ 7 !} \\cdot y^{2} z^{7} + \\frac{ 225 }{ 6 !} \\cdot y^{3} z^{6} + \\frac{ 10 }{ 5 !} \\cdot y^{4} z^{5}\\)" ], "text/latex": [ "$\\displaystyle \\frac{1}{{\\left(-z + 1\\right)}^{y}} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot y z + \\frac{ 1 }{ 2 !} \\cdot y z^{2} + \\frac{ 2 }{ 3 !} \\cdot y z^{3} + \\frac{ 1 }{ 2 !} \\cdot y^{2} z^{2} + \\frac{ 6 }{ 4 !} \\cdot y z^{4} + \\frac{ 3 }{ 3 !} \\cdot y^{2} z^{3} + \\frac{ 24 }{ 5 !} \\cdot y z^{5} + \\frac{ 11 }{ 4 !} \\cdot y^{2} z^{4} + \\frac{ 1 }{ 3 !} \\cdot y^{3} z^{3} + \\frac{ 120 }{ 6 !} \\cdot y z^{6} + \\frac{ 50 }{ 5 !} \\cdot y^{2} z^{5} + \\frac{ 6 }{ 4 !} \\cdot y^{3} z^{4} + \\frac{ 720 }{ 7 !} \\cdot y z^{7} + \\frac{ 274 }{ 6 !} \\cdot y^{2} z^{6} + \\frac{ 35 }{ 5 !} \\cdot y^{3} z^{5} + \\frac{ 1 }{ 4 !} \\cdot y^{4} z^{4} + \\frac{ 5040 }{ 8 !} \\cdot y z^{8} + \\frac{ 1764 }{ 7 !} \\cdot y^{2} z^{7} + \\frac{ 225 }{ 6 !} \\cdot y^{3} z^{6} + \\frac{ 10 }{ 5 !} \\cdot y^{4} z^{5}$" ], "text/plain": [ "1/((-z + 1)^y) '=\\t' \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot y z + \\frac{ 1 }{ 2 !} \\cdot y z^{2} + \\frac{ 2 }{ 3 !} \\cdot y z^{3} + \\frac{ 1 }{ 2 !} \\cdot y^{2} z^{2} + \\frac{ 6 }{ 4 !} \\cdot y z^{4} + \\frac{ 3 }{ 3 !} \\cdot y^{2} z^{3} + \\frac{ 24 }{ 5 !} \\cdot y z^{5} + \\frac{ 11 }{ 4 !} \\cdot y^{2} z^{4} + \\frac{ 1 }{ 3 !} \\cdot y^{3} z^{3} + \\frac{ 120 }{ 6 !} \\cdot y z^{6} + \\frac{ 50 }{ 5 !} \\cdot y^{2} z^{5} + \\frac{ 6 }{ 4 !} \\cdot y^{3} z^{4} + \\frac{ 720 }{ 7 !} \\cdot y z^{7} + \\frac{ 274 }{ 6 !} \\cdot y^{2} z^{6} + \\frac{ 35 }{ 5 !} \\cdot y^{3} z^{5} + \\frac{ 1 }{ 4 !} \\cdot y^{4} z^{4} + \\frac{ 5040 }{ 8 !} \\cdot y z^{8} + \\frac{ 1764 }{ 7 !} \\cdot y^{2} z^{7} + \\frac{ 225 }{ 6 !} \\cdot y^{3} z^{6} + \\frac{ 10 }{ 5 !} \\cdot y^{4} z^{5}" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# First examine EGF for permutations by number of cycles\n", "GFinfo(-log(1-z), exponential=True)\n", "\n", "# Then do bivariate semi-exponential GF for permutations by length and number of cycles\n", "GFinfo2D((1-z)^(-y),var1=y, var2=z,semi=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.49 - Involutions" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|$" ], "text/plain": [ "'This exponential generating function has an expansion beginning'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle e^{\\left(\\frac{1}{2} \\, z^{2} + z\\right)} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 2 }{ 2 !} \\cdot z^{2} + \\frac{ 4 }{ 3 !} \\cdot z^{3} + \\frac{ 10 }{ 4 !} \\cdot z^{4} + \\frac{ 26 }{ 5 !} \\cdot z^{5} + \\frac{ 76 }{ 6 !} \\cdot z^{6} + \\frac{ 232 }{ 7 !} \\cdot z^{7} + \\frac{ 764 }{ 8 !} \\cdot z^{8} + \\frac{ 2620 }{ 9 !} \\cdot z^{9}\\)" ], "text/latex": [ "$\\displaystyle e^{\\left(\\frac{1}{2} \\, z^{2} + z\\right)} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 2 }{ 2 !} \\cdot z^{2} + \\frac{ 4 }{ 3 !} \\cdot z^{3} + \\frac{ 10 }{ 4 !} \\cdot z^{4} + \\frac{ 26 }{ 5 !} \\cdot z^{5} + \\frac{ 76 }{ 6 !} \\cdot z^{6} + \\frac{ 232 }{ 7 !} \\cdot z^{7} + \\frac{ 764 }{ 8 !} \\cdot z^{8} + \\frac{ 2620 }{ 9 !} \\cdot z^{9}$" ], "text/plain": [ "e^(1/2*z^2 + z) '=\\t' \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 2 }{ 2 !} \\cdot z^{2} + \\frac{ 4 }{ 3 !} \\cdot z^{3} + \\frac{ 10 }{ 4 !} \\cdot z^{4} + \\frac{ 26 }{ 5 !} \\cdot z^{5} + \\frac{ 76 }{ 6 !} \\cdot z^{6} + \\frac{ 232 }{ 7 !} \\cdot z^{7} + \\frac{ 764 }{ 8 !} \\cdot z^{8} + \\frac{ 2620 }{ 9 !} \\cdot z^{9}" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "GFinfo(exp(z+z^2/2),exponential=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.50 - Set Partitions" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|$" ], "text/plain": [ "'This exponential generating function has an expansion beginning'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle e^{\\left(y {\\left(e^{z} - 1\\right)}\\right)} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot y z + \\frac{ 1 }{ 2 !} \\cdot y z^{2} + \\frac{ 1 }{ 3 !} \\cdot y z^{3} + \\frac{ 1 }{ 2 !} \\cdot y^{2} z^{2} + \\frac{ 1 }{ 4 !} \\cdot y z^{4} + \\frac{ 3 }{ 3 !} \\cdot y^{2} z^{3} + \\frac{ 1 }{ 5 !} \\cdot y z^{5} + \\frac{ 7 }{ 4 !} \\cdot y^{2} z^{4} + \\frac{ 1 }{ 3 !} \\cdot y^{3} z^{3} + \\frac{ 1 }{ 6 !} \\cdot y z^{6} + \\frac{ 15 }{ 5 !} \\cdot y^{2} z^{5} + \\frac{ 6 }{ 4 !} \\cdot y^{3} z^{4} + \\frac{ 1 }{ 7 !} \\cdot y z^{7} + \\frac{ 31 }{ 6 !} \\cdot y^{2} z^{6} + \\frac{ 25 }{ 5 !} \\cdot y^{3} z^{5} + \\frac{ 1 }{ 4 !} \\cdot y^{4} z^{4} + \\frac{ 1 }{ 8 !} \\cdot y z^{8} + \\frac{ 63 }{ 7 !} \\cdot y^{2} z^{7} + \\frac{ 90 }{ 6 !} \\cdot y^{3} z^{6} + \\frac{ 10 }{ 5 !} \\cdot y^{4} z^{5}\\)" ], "text/latex": [ "$\\displaystyle e^{\\left(y {\\left(e^{z} - 1\\right)}\\right)} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot y z + \\frac{ 1 }{ 2 !} \\cdot y z^{2} + \\frac{ 1 }{ 3 !} \\cdot y z^{3} + \\frac{ 1 }{ 2 !} \\cdot y^{2} z^{2} + \\frac{ 1 }{ 4 !} \\cdot y z^{4} + \\frac{ 3 }{ 3 !} \\cdot y^{2} z^{3} + \\frac{ 1 }{ 5 !} \\cdot y z^{5} + \\frac{ 7 }{ 4 !} \\cdot y^{2} z^{4} + \\frac{ 1 }{ 3 !} \\cdot y^{3} z^{3} + \\frac{ 1 }{ 6 !} \\cdot y z^{6} + \\frac{ 15 }{ 5 !} \\cdot y^{2} z^{5} + \\frac{ 6 }{ 4 !} \\cdot y^{3} z^{4} + \\frac{ 1 }{ 7 !} \\cdot y z^{7} + \\frac{ 31 }{ 6 !} \\cdot y^{2} z^{6} + \\frac{ 25 }{ 5 !} \\cdot y^{3} z^{5} + \\frac{ 1 }{ 4 !} \\cdot y^{4} z^{4} + \\frac{ 1 }{ 8 !} \\cdot y z^{8} + \\frac{ 63 }{ 7 !} \\cdot y^{2} z^{7} + \\frac{ 90 }{ 6 !} \\cdot y^{3} z^{6} + \\frac{ 10 }{ 5 !} \\cdot y^{4} z^{5}$" ], "text/plain": [ "e^(y*(e^z - 1)) '=\\t' \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot y z + \\frac{ 1 }{ 2 !} \\cdot y z^{2} + \\frac{ 1 }{ 3 !} \\cdot y z^{3} + \\frac{ 1 }{ 2 !} \\cdot y^{2} z^{2} + \\frac{ 1 }{ 4 !} \\cdot y z^{4} + \\frac{ 3 }{ 3 !} \\cdot y^{2} z^{3} + \\frac{ 1 }{ 5 !} \\cdot y z^{5} + \\frac{ 7 }{ 4 !} \\cdot y^{2} z^{4} + \\frac{ 1 }{ 3 !} \\cdot y^{3} z^{3} + \\frac{ 1 }{ 6 !} \\cdot y z^{6} + \\frac{ 15 }{ 5 !} \\cdot y^{2} z^{5} + \\frac{ 6 }{ 4 !} \\cdot y^{3} z^{4} + \\frac{ 1 }{ 7 !} \\cdot y z^{7} + \\frac{ 31 }{ 6 !} \\cdot y^{2} z^{6} + \\frac{ 25 }{ 5 !} \\cdot y^{3} z^{5} + \\frac{ 1 }{ 4 !} \\cdot y^{4} z^{4} + \\frac{ 1 }{ 8 !} \\cdot y z^{8} + \\frac{ 63 }{ 7 !} \\cdot y^{2} z^{7} + \\frac{ 90 }{ 6 !} \\cdot y^{3} z^{6} + \\frac{ 10 }{ 5 !} \\cdot y^{4} z^{5}" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Substituting y = 1 gives the univariate EGF for set partitions\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|$" ], "text/plain": [ "'This exponential generating function has an expansion beginning'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle e^{\\left(e^{z} - 1\\right)} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 2 }{ 2 !} \\cdot z^{2} + \\frac{ 5 }{ 3 !} \\cdot z^{3} + \\frac{ 15 }{ 4 !} \\cdot z^{4} + \\frac{ 52 }{ 5 !} \\cdot z^{5} + \\frac{ 203 }{ 6 !} \\cdot z^{6} + \\frac{ 877 }{ 7 !} \\cdot z^{7} + \\frac{ 4140 }{ 8 !} \\cdot z^{8} + \\frac{ 21147 }{ 9 !} \\cdot z^{9}\\)" ], "text/latex": [ "$\\displaystyle e^{\\left(e^{z} - 1\\right)} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 2 }{ 2 !} \\cdot z^{2} + \\frac{ 5 }{ 3 !} \\cdot z^{3} + \\frac{ 15 }{ 4 !} \\cdot z^{4} + \\frac{ 52 }{ 5 !} \\cdot z^{5} + \\frac{ 203 }{ 6 !} \\cdot z^{6} + \\frac{ 877 }{ 7 !} \\cdot z^{7} + \\frac{ 4140 }{ 8 !} \\cdot z^{8} + \\frac{ 21147 }{ 9 !} \\cdot z^{9}$" ], "text/plain": [ "e^(e^z - 1) '=\\t' \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 2 }{ 2 !} \\cdot z^{2} + \\frac{ 5 }{ 3 !} \\cdot z^{3} + \\frac{ 15 }{ 4 !} \\cdot z^{4} + \\frac{ 52 }{ 5 !} \\cdot z^{5} + \\frac{ 203 }{ 6 !} \\cdot z^{6} + \\frac{ 877 }{ 7 !} \\cdot z^{7} + \\frac{ 4140 }{ 8 !} \\cdot z^{8} + \\frac{ 21147 }{ 9 !} \\cdot z^{9}" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "F = exp(y*(exp(z) - 1))\n", "GFinfo2D(F,var1=y, var2=z,semi=True)\n", "print(\"Substituting y = 1 gives the univariate EGF for set partitions\")\n", "G = F.subs(y=1)\n", "GFinfo(G,exponential=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.51 - Partitions into Ordered Sets" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|$" ], "text/plain": [ "'This exponential generating function has an expansion beginning'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle e^{\\left(-\\frac{y z}{z - 1}\\right)} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot y z + \\frac{ 2 }{ 2 !} \\cdot y z^{2} + \\frac{ 6 }{ 3 !} \\cdot y z^{3} + \\frac{ 1 }{ 2 !} \\cdot y^{2} z^{2} + \\frac{ 24 }{ 4 !} \\cdot y z^{4} + \\frac{ 6 }{ 3 !} \\cdot y^{2} z^{3} + \\frac{ 120 }{ 5 !} \\cdot y z^{5} + \\frac{ 36 }{ 4 !} \\cdot y^{2} z^{4} + \\frac{ 1 }{ 3 !} \\cdot y^{3} z^{3} + \\frac{ 720 }{ 6 !} \\cdot y z^{6} + \\frac{ 240 }{ 5 !} \\cdot y^{2} z^{5} + \\frac{ 12 }{ 4 !} \\cdot y^{3} z^{4} + \\frac{ 5040 }{ 7 !} \\cdot y z^{7} + \\frac{ 1800 }{ 6 !} \\cdot y^{2} z^{6} + \\frac{ 120 }{ 5 !} \\cdot y^{3} z^{5} + \\frac{ 1 }{ 4 !} \\cdot y^{4} z^{4} + \\frac{ 40320 }{ 8 !} \\cdot y z^{8} + \\frac{ 15120 }{ 7 !} \\cdot y^{2} z^{7} + \\frac{ 1200 }{ 6 !} \\cdot y^{3} z^{6} + \\frac{ 20 }{ 5 !} \\cdot y^{4} z^{5}\\)" ], "text/latex": [ "$\\displaystyle e^{\\left(-\\frac{y z}{z - 1}\\right)} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot y z + \\frac{ 2 }{ 2 !} \\cdot y z^{2} + \\frac{ 6 }{ 3 !} \\cdot y z^{3} + \\frac{ 1 }{ 2 !} \\cdot y^{2} z^{2} + \\frac{ 24 }{ 4 !} \\cdot y z^{4} + \\frac{ 6 }{ 3 !} \\cdot y^{2} z^{3} + \\frac{ 120 }{ 5 !} \\cdot y z^{5} + \\frac{ 36 }{ 4 !} \\cdot y^{2} z^{4} + \\frac{ 1 }{ 3 !} \\cdot y^{3} z^{3} + \\frac{ 720 }{ 6 !} \\cdot y z^{6} + \\frac{ 240 }{ 5 !} \\cdot y^{2} z^{5} + \\frac{ 12 }{ 4 !} \\cdot y^{3} z^{4} + \\frac{ 5040 }{ 7 !} \\cdot y z^{7} + \\frac{ 1800 }{ 6 !} \\cdot y^{2} z^{6} + \\frac{ 120 }{ 5 !} \\cdot y^{3} z^{5} + \\frac{ 1 }{ 4 !} \\cdot y^{4} z^{4} + \\frac{ 40320 }{ 8 !} \\cdot y z^{8} + \\frac{ 15120 }{ 7 !} \\cdot y^{2} z^{7} + \\frac{ 1200 }{ 6 !} \\cdot y^{3} z^{6} + \\frac{ 20 }{ 5 !} \\cdot y^{4} z^{5}$" ], "text/plain": [ "e^(-y*z/(z - 1)) '=\\t' \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot y z + \\frac{ 2 }{ 2 !} \\cdot y z^{2} + \\frac{ 6 }{ 3 !} \\cdot y z^{3} + \\frac{ 1 }{ 2 !} \\cdot y^{2} z^{2} + \\frac{ 24 }{ 4 !} \\cdot y z^{4} + \\frac{ 6 }{ 3 !} \\cdot y^{2} z^{3} + \\frac{ 120 }{ 5 !} \\cdot y z^{5} + \\frac{ 36 }{ 4 !} \\cdot y^{2} z^{4} + \\frac{ 1 }{ 3 !} \\cdot y^{3} z^{3} + \\frac{ 720 }{ 6 !} \\cdot y z^{6} + \\frac{ 240 }{ 5 !} \\cdot y^{2} z^{5} + \\frac{ 12 }{ 4 !} \\cdot y^{3} z^{4} + \\frac{ 5040 }{ 7 !} \\cdot y z^{7} + \\frac{ 1800 }{ 6 !} \\cdot y^{2} z^{6} + \\frac{ 120 }{ 5 !} \\cdot y^{3} z^{5} + \\frac{ 1 }{ 4 !} \\cdot y^{4} z^{4} + \\frac{ 40320 }{ 8 !} \\cdot y z^{8} + \\frac{ 15120 }{ 7 !} \\cdot y^{2} z^{7} + \\frac{ 1200 }{ 6 !} \\cdot y^{3} z^{6} + \\frac{ 20 }{ 5 !} \\cdot y^{4} z^{5}" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Substituting y = 1 gives the univariate EGF\n" ] }, { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|$" ], "text/plain": [ "'This exponential generating function has an expansion beginning'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle e^{\\left(-\\frac{z}{z - 1}\\right)} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 3 }{ 2 !} \\cdot z^{2} + \\frac{ 13 }{ 3 !} \\cdot z^{3} + \\frac{ 73 }{ 4 !} \\cdot z^{4} + \\frac{ 501 }{ 5 !} \\cdot z^{5} + \\frac{ 4051 }{ 6 !} \\cdot z^{6} + \\frac{ 37633 }{ 7 !} \\cdot z^{7} + \\frac{ 394353 }{ 8 !} \\cdot z^{8} + \\frac{ 4596553 }{ 9 !} \\cdot z^{9}\\)" ], "text/latex": [ "$\\displaystyle e^{\\left(-\\frac{z}{z - 1}\\right)} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 3 }{ 2 !} \\cdot z^{2} + \\frac{ 13 }{ 3 !} \\cdot z^{3} + \\frac{ 73 }{ 4 !} \\cdot z^{4} + \\frac{ 501 }{ 5 !} \\cdot z^{5} + \\frac{ 4051 }{ 6 !} \\cdot z^{6} + \\frac{ 37633 }{ 7 !} \\cdot z^{7} + \\frac{ 394353 }{ 8 !} \\cdot z^{8} + \\frac{ 4596553 }{ 9 !} \\cdot z^{9}$" ], "text/plain": [ "e^(-z/(z - 1)) '=\\t' \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 3 }{ 2 !} \\cdot z^{2} + \\frac{ 13 }{ 3 !} \\cdot z^{3} + \\frac{ 73 }{ 4 !} \\cdot z^{4} + \\frac{ 501 }{ 5 !} \\cdot z^{5} + \\frac{ 4051 }{ 6 !} \\cdot z^{6} + \\frac{ 37633 }{ 7 !} \\cdot z^{7} + \\frac{ 394353 }{ 8 !} \\cdot z^{8} + \\frac{ 4596553 }{ 9 !} \\cdot z^{9}" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "F = exp(y*z/(1-z))\n", "GFinfo2D(F,var1=y, var2=z,semi=True)\n", "print(\"Substituting y = 1 gives the univariate EGF\")\n", "G = F.subs(y=1)\n", "GFinfo(G,exponential=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.52 - 2-Regular Graphs" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|$" ], "text/plain": [ "'This exponential generating function has an expansion beginning'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle \\frac{e^{\\left(-\\frac{1}{4} \\, z^{2} - \\frac{1}{2} \\, z\\right)}}{\\sqrt{-z + 1}} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 3 !} \\cdot z^{3} + \\frac{ 3 }{ 4 !} \\cdot z^{4} + \\frac{ 12 }{ 5 !} \\cdot z^{5} + \\frac{ 70 }{ 6 !} \\cdot z^{6} + \\frac{ 465 }{ 7 !} \\cdot z^{7} + \\frac{ 3507 }{ 8 !} \\cdot z^{8} + \\frac{ 30016 }{ 9 !} \\cdot z^{9}\\)" ], "text/latex": [ "$\\displaystyle \\frac{e^{\\left(-\\frac{1}{4} \\, z^{2} - \\frac{1}{2} \\, z\\right)}}{\\sqrt{-z + 1}} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 3 !} \\cdot z^{3} + \\frac{ 3 }{ 4 !} \\cdot z^{4} + \\frac{ 12 }{ 5 !} \\cdot z^{5} + \\frac{ 70 }{ 6 !} \\cdot z^{6} + \\frac{ 465 }{ 7 !} \\cdot z^{7} + \\frac{ 3507 }{ 8 !} \\cdot z^{8} + \\frac{ 30016 }{ 9 !} \\cdot z^{9}$" ], "text/plain": [ "e^(-1/4*z^2 - 1/2*z)/sqrt(-z + 1) '=\\t' \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 3 !} \\cdot z^{3} + \\frac{ 3 }{ 4 !} \\cdot z^{4} + \\frac{ 12 }{ 5 !} \\cdot z^{5} + \\frac{ 70 }{ 6 !} \\cdot z^{6} + \\frac{ 465 }{ 7 !} \\cdot z^{7} + \\frac{ 3507 }{ 8 !} \\cdot z^{8} + \\frac{ 30016 }{ 9 !} \\cdot z^{9}" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "GFinfo(exp(-z/2-z^2/4)/sqrt(1-z),exponential=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.53 - Surjections" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|\\)" ], "text/latex": [ "$\\displaystyle \\verb|This|\\verb| |\\verb|exponential|\\verb| |\\verb|generating|\\verb| |\\verb|function|\\verb| |\\verb|has|\\verb| |\\verb|an|\\verb| |\\verb|expansion|\\verb| |\\verb|beginning|$" ], "text/plain": [ "'This exponential generating function has an expansion beginning'" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "\\(\\displaystyle -\\frac{1}{e^{z} - 2} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 3 }{ 2 !} \\cdot z^{2} + \\frac{ 13 }{ 3 !} \\cdot z^{3} + \\frac{ 75 }{ 4 !} \\cdot z^{4} + \\frac{ 541 }{ 5 !} \\cdot z^{5} + \\frac{ 4683 }{ 6 !} \\cdot z^{6} + \\frac{ 47293 }{ 7 !} \\cdot z^{7} + \\frac{ 545835 }{ 8 !} \\cdot z^{8} + \\frac{ 7087261 }{ 9 !} \\cdot z^{9}\\)" ], "text/latex": [ "$\\displaystyle -\\frac{1}{e^{z} - 2} \\verb|=\t| \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 3 }{ 2 !} \\cdot z^{2} + \\frac{ 13 }{ 3 !} \\cdot z^{3} + \\frac{ 75 }{ 4 !} \\cdot z^{4} + \\frac{ 541 }{ 5 !} \\cdot z^{5} + \\frac{ 4683 }{ 6 !} \\cdot z^{6} + \\frac{ 47293 }{ 7 !} \\cdot z^{7} + \\frac{ 545835 }{ 8 !} \\cdot z^{8} + \\frac{ 7087261 }{ 9 !} \\cdot z^{9}$" ], "text/plain": [ "-1/(e^z - 2) '=\\t' \\frac{ 1 }{ 0 !} \\cdot 1 + \\frac{ 1 }{ 1 !} \\cdot z + \\frac{ 3 }{ 2 !} \\cdot z^{2} + \\frac{ 13 }{ 3 !} \\cdot z^{3} + \\frac{ 75 }{ 4 !} \\cdot z^{4} + \\frac{ 541 }{ 5 !} \\cdot z^{5} + \\frac{ 4683 }{ 6 !} \\cdot z^{6} + \\frac{ 47293 }{ 7 !} \\cdot z^{7} + \\frac{ 545835 }{ 8 !} \\cdot z^{8} + \\frac{ 7087261 }{ 9 !} \\cdot z^{9}" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "GFinfo(1/(2-exp(z)),exponential=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 10.1", "language": "sage", "name": "sagemath-10.1" }, "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.11.1" } }, "nbformat": 4, "nbformat_minor": 4 }