{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 1.2 (The Catalan Generating Function)\n", "Some computations with the Catalan generating function. \n", "*Requirements: Internet access (partially)*" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\verb|C(z)|\\phantom{\\verb!x!}\\verb|=| -\\frac{\\sqrt{-4 \\, z + 1} - 1}{2 \\, z}\n", "\\end{math}" ], "text/plain": [ "'C(z) = ' -1/2*(sqrt(-4*z + 1) - 1)/z" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# First, define z as a variable\n", "var('z')\n", "\n", "# Next, define the Catalan generating function\n", "C = (1-sqrt(1-4*z))/(2*z)\n", "show(\"C(z) = \", C)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\verb|C(z)|\\phantom{\\verb!x!}\\verb|=| 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)\n", "\\end{math}" ], "text/plain": [ "'C(z) = ' 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": [ "# The coefficients of the power series expansion of C at the origin form the Catalan numbers\n", "ser = C.series(z,10)\n", "show(\"C(z) = \",ser)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0: A000108: Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).\n", "1: A120588: G.f. is 1 + x*c(x), where c(x) is the g.f. of the Catalan numbers (A000108).\n", "2: A211216: Expansion of (1-8*x+21*x^2-20*x^3+5*x^4)/(1-9*x+28*x^2-35*x^3+15*x^4-x^5).\n" ] } ], "source": [ "# Search the Online Encyclopedia of Integer Sequences for sequences with this start\n", "# Note: From here down Sage requires an internet connection\n", "oe = oeis(ser.list())\n", "print(oe)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "A000108: Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!)." ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# There are a few sequences where the first 10 terms appear, generating more terms narrows down the correct sequence\n", "oe[0]" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0: a(n) = binomial(2*n, n) - binomial(2*n, n-1).\n", "1: a(n) = Sum_{k=0..n-1} a(k)a(n-1-k).\n", "2: a(n) = Product_{k=2..n} (1 + n/k), if n > 1.\n", "3: G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x). G.f. A(x) satisfies A = 1 + x*A^2.\n", "4: a(n+1) = Sum_{i} binomial(n, 2*i)*2^(n-2*i)*a(i). - Touchard\n", "5: D-finite with recurrence: 2*(2*n-1)*a(n-1) = (n+1)*a(n).\n", "6: It is known that a(n) is odd if and only if n=2^k-1, k=0, 1, 2, 3, ... - _Emeric Deutsch_, Aug 04 2002, corrected by _M. F. Hasler_, Nov 08 2015\n", "7: Using the Stirling approximation in A000142 we get the asymptotic expansion a(n) ~ 4^n / (sqrt(Pi * n) * (n + 1)). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 13 2001\n", "8: Integral representation: a(n) = (1/(2*Pi))*Integral_{x=0..4} x^n*sqrt((4-x)/x). - _Karol A. Penson_, Apr 12 2001" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Here are a few of the formulas for the Catalan numbers available on the OEIS\n", "oe[0].formulas()[1:10]" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0: The solution to Schröder's first problem. A very large number of combinatorial interpretations are known - see references, esp. Stanley, Enumerative Combinatorics, Volume 2. This is probably the longest entry in the OEIS, and rightly so.\n", "1: Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).\n", "2: Consider all the binomial(2n,n) paths on squared paper that (i) start at (0, 0), (ii) end at (2n, 0) and (iii) at each step, either make a (+1,+1) step or a (+1,-1) step. Then the number of such paths that never go below the x-axis (Dyck paths) is C(n). [Chung-Feller]\n", "3: Number of noncrossing partitions of the n-set. For example, of the 15 set partitions of the 4-set, only [{13},{24}] is crossing, so there are a(4)=14 noncrossing partitions of 4 elements. - _Joerg Arndt_, Jul 11 2011\n", "4: a(n-1) is the number of ways of expressing an n-cycle in the symmetric group S_n as a product of n-1 transpositions (u_1,v_1)*(u_2,v_2)*...*(u_{n-1},v_{n-1}) where u_k <= u_j and v_k <= v_j for k < j; see example. If the condition is dropped, one obtains A000272. - _Joerg Arndt_ and Greg Stevenson, Jul 11 2011\n", "5: a(n) is the number of ordered rooted trees with n nodes, not including the root. See the Conway-Guy reference where these rooted ordered trees are called plane bushes. See also the Bergeron et al. reference, Example 4, p. 167. - _Wolfdieter Lang_, Aug 07 2007\n", "6: As shown in the paper from Beineke and Pippert (1971), a(n-2)=D(n) is the number of labeled dissections of a disk, related to the number R(n)=A001761(n-2) of labeled planar 2-trees having n vertices and rooted at a given exterior edge, by the formula D(n)=R(n)/(n-2)!. - _M. F. Hasler_, Feb 22 2012\n", "7: Shifts one place left when convolved with itself.\n", "8: For n >= 1 a(n) is also the number of rooted bicolored unicellular maps of genus 0 on n edges. - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 15 2001" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Here are a few of the examples of Catalan numbers listed on the OEIS\n", "oe[0].comments()[1:10]" ] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "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 }