{ "cells": [ { "cell_type": "markdown", "id": "61b17372", "metadata": {}, "source": [ "# Introduction to Combinatorial Objects in SageMath\n", "### A hands-on introduction for beginners\n", "\n", "**Goal of this notebook:** get a feel for *what exists* in Sage's combinatorics library, and *how to get at it* — construct objects, count them, list them, pick a random one, and check their properties.\n", "\n", "We will look at:\n", "\n", "1. The general philosophy: **combinatorial classes**\n", "2. `Permutations`\n", "3. `DyckWords` (and why Catalan numbers are everywhere), including `ascii_art`\n", "4. `BinaryTrees` and the Dyck-word/tree bijection, also with `ascii_art`\n", "5. `Compositions`\n", "6. `Partitions`\n", "7. `SetPartitions`\n", "8. `Words`\n", "9. General recipes that work almost everywhere in `sage.combinat`\n", "10. Where to go next\n", "11. Glimpse at generating functions and lattice paths\n", "\n", "> Tip: in a Sage/Jupyter cell you can always type an object name followed by a dot and press **Tab** to see all available methods, or put a **`?`** after something to get its documentation, e.g. `Permutations?`.\n" ] }, { "cell_type": "markdown", "id": "24039d8f", "metadata": {}, "source": [ "## 1. The general philosophy: combinatorial classes\n", "\n", "Almost every family of combinatorial objects in Sage (permutations, partitions, trees, tableaux, words, ...) is presented through the same small set of ideas:\n", "\n", "- There is a **class/parent** that represents *the whole family* (possibly restricted by a size or other parameter), e.g. `Permutations(5)` represents *all* permutations of $\\{1,\\dots,5\\}$.\n", "- That parent behaves like a (possibly infinite) **set/container**: you can ask for its `.cardinality()`, iterate over it, get `.list()`, ask `.random_element()`, and so on.\n", "- Individual **elements** of that family are actual Sage objects with their own methods (e.g. a permutation knows its own number of inversions, a Dyck word knows its own area, etc.).\n", "\n", "So the recipe is always:\n", "\n", "```\n", "Family = SomeCombinatorialFamily(parameters) # the parent / class\n", "Family.cardinality() # how many are there?\n", "Family.list() # give me all of them (if feasible)\n", "Family.random_element() # give me one at random\n", "x = Family.an_element() # give me *some* concrete element\n", "x.some_method() # ask the element about itself\n", "```\n", "\n", "Keep this pattern in mind, it will repeat for every family below.\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "21b9966a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Standard permutations of 3" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# A quick warm-up with this pattern, using Permutations of {1,2,3}\n", "P = Permutations(3)\n", "P\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "fc5b6851", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.cardinality() # should be 3! = 6\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "f1af8a74", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.list() # all of them, as actual Permutation objects\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "7d761fc6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2, 1, 3]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.random_element() # a uniformly random permutation of size 3\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "560f38be-bd3f-467d-be04-99007e7375e6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[3, 1, 2]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.an_element() # a representative that is not random (and often trivial)" ] }, { "cell_type": "markdown", "id": "9b8b0389", "metadata": {}, "source": [ "## 2. Permutations\n", "\n", "`Permutations(n)` is the set of permutations of $\\{1,\\dots,n\\}$. There are many variants:\n", "\n", "- `Permutations()` — permutations of arbitrary size (an infinite family, used mostly to build individual permutations)\n", "- `Permutations(n)` — permutations of $\\{1,\\dots,n\\}$\n", "- `Permutations(n, k)` — permutations of $\\{1,\\dots,n\\}$ with exactly $k$ *something* depending on context (e.g. length-$k$ partial permutations) — check `Permutations?` for the exact variants\n", "- `Permutations([3,1,2,5,...])` — permutations of an arbitrary list of values\n", "\n", "An individual permutation can be built directly, e.g. `Permutation([2,1,3])`, or obtained from `Permutations(n)`.\n" ] }, { "cell_type": "code", "execution_count": 13, "id": "3d3e95fd-9f8e-4557-a63f-a26b6ccdee44", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[31mInit signature:\u001b[39m Permutations(self, x=\u001b[32m0\u001b[39m, *args, **kwds)\n", "\u001b[31mDocstring:\u001b[39m \n", " Permutations.\n", "\n", " \"Permutations(n)\" returns the class of permutations of \"n\", if \"n\"\n", " is an integer, list, set, or string.\n", "\n", " \"Permutations(n, k)\" returns the class of length-\"k\" partial\n", " permutations of \"n\" (where \"n\" is any of the above things); \"k\"\n", " must be a nonnegative integer. A length-k partial permutation of n\n", " is defined as a k-tuple of pairwise distinct elements of \\{ 1, 2,\n", " ..., n \\}.\n", "\n", " Valid keyword arguments are: 'descents', 'bruhat_smaller',\n", " 'bruhat_greater', 'recoils_finer', 'recoils_fatter', 'recoils', and\n", " 'avoiding'. With the exception of 'avoiding', you cannot specify\n", " \"n\" or \"k\" along with a keyword.\n", "\n", " \"Permutations(descents=(list,n))\" returns the class of permutations\n", " of n with descents in the positions specified by \"list\". This uses\n", " the slightly nonstandard convention that the images of 1,2,...,n\n", " under the permutation are regarded as positions 0,1,...,n-1, so for\n", " example the presence of 1 in \"list\" signifies that the permutations\n", " \\pi should satisfy \\pi(2) > \\pi(3). Note that \"list\" is supposed to\n", " be a list of positions of the descents, not the descents\n", " composition. It does *not* return the class of permutations with\n", " descents composition \"list\".\n", "\n", " \"Permutations(bruhat_smaller=p)\" and\n", " \"Permutations(bruhat_greater=p)\" return the class of permutations\n", " smaller-or-equal or greater-or-equal, respectively, than the given\n", " permutation \"p\" in the Bruhat order. (The Bruhat order is defined\n", " in \"bruhat_lequal()\". It is also referred to as the *strong* Bruhat\n", " order.)\n", "\n", " \"Permutations(recoils=p)\" returns the class of permutations whose\n", " recoils composition is \"p\". Unlike the \"descents=(list, n)\" syntax,\n", " this actually takes a *composition* as input.\n", "\n", " \"Permutations(recoils_fatter=p)\" and\n", " \"Permutations(recoils_finer=p)\" return the class of permutations\n", " whose recoils composition is fatter or finer, respectively, than\n", " the given composition \"p\".\n", "\n", " \"Permutations(n, avoiding=P)\" returns the class of permutations of\n", " \"n\" avoiding \"P\". Here \"P\" may be a single permutation or a list of\n", " permutations; the returned class will avoid all patterns in \"P\".\n", "\n", " EXAMPLES:\n", "\n", " sage: p = Permutations(3); p\n", " Standard permutations of 3\n", " sage: p.list()\n", " [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]\n", "\n", " sage: p = Permutations(3, 2); p\n", " Permutations of {1,...,3} of length 2\n", " sage: p.list()\n", " [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]\n", "\n", " sage: p = Permutations(['c', 'a', 't']); p\n", " Permutations of the set ['c', 'a', 't']\n", " sage: p.list()\n", " [['c', 'a', 't'],\n", " ['c', 't', 'a'],\n", " ['a', 'c', 't'],\n", " ['a', 't', 'c'],\n", " ['t', 'c', 'a'],\n", " ['t', 'a', 'c']]\n", "\n", " sage: p = Permutations(['c', 'a', 't'], 2); p\n", " Permutations of the set ['c', 'a', 't'] of length 2\n", " sage: p.list()\n", " [['c', 'a'], ['c', 't'], ['a', 'c'], ['a', 't'], ['t', 'c'], ['t', 'a']]\n", "\n", " sage: p = Permutations([1,1,2]); p\n", " Permutations of the multi-set [1, 1, 2]\n", " sage: p.list()\n", " [[1, 1, 2], [1, 2, 1], [2, 1, 1]]\n", "\n", " sage: p = Permutations([1,1,2], 2); p\n", " Permutations of the multi-set [1, 1, 2] of length 2\n", " sage: p.list()\n", " [[1, 1], [1, 2], [2, 1]]\n", "\n", " sage: p = Permutations(descents=([1], 4)); p\n", " Standard permutations of 4 with descents [1]\n", " sage: p.list()\n", " [[2, 4, 1, 3], [3, 4, 1, 2], [1, 4, 2, 3], [1, 3, 2, 4], [2, 3, 1, 4]]\n", "\n", " sage: p = Permutations(bruhat_smaller=[1,3,2,4]); p\n", " Standard permutations that are less than or equal\n", " to [1, 3, 2, 4] in the Bruhat order\n", " sage: p.list()\n", " [[1, 2, 3, 4], [1, 3, 2, 4]]\n", "\n", " sage: p = Permutations(bruhat_greater=[4,2,3,1]); p\n", " Standard permutations that are greater than or equal\n", " to [4, 2, 3, 1] in the Bruhat order\n", " sage: p.list()\n", " [[4, 2, 3, 1], [4, 3, 2, 1]]\n", "\n", " sage: p = Permutations(recoils_finer=[2,1]); p\n", " Standard permutations whose recoils composition is finer than [2, 1]\n", " sage: p.list()\n", " [[3, 1, 2], [1, 2, 3], [1, 3, 2]]\n", "\n", " sage: p = Permutations(recoils_fatter=[2,1]); p\n", " Standard permutations whose recoils composition is fatter than [2, 1]\n", " sage: p.list()\n", " [[3, 1, 2], [3, 2, 1], [1, 3, 2]]\n", "\n", " sage: p = Permutations(recoils=[2,1]); p\n", " Standard permutations whose recoils composition is [2, 1]\n", " sage: p.list()\n", " [[3, 1, 2], [1, 3, 2]]\n", "\n", " sage: p = Permutations(4, avoiding=[1,3,2]); p\n", " Standard permutations of 4 avoiding [[1, 3, 2]]\n", " sage: p.list()\n", " [[4, 1, 2, 3],\n", " [4, 2, 1, 3],\n", " [4, 2, 3, 1],\n", " [4, 3, 1, 2],\n", " [4, 3, 2, 1],\n", " [3, 4, 1, 2],\n", " [3, 4, 2, 1],\n", " [2, 3, 4, 1],\n", " [3, 2, 4, 1],\n", " [1, 2, 3, 4],\n", " [2, 1, 3, 4],\n", " [2, 3, 1, 4],\n", " [3, 1, 2, 4],\n", " [3, 2, 1, 4]]\n", "\n", " sage: p = Permutations(5, avoiding=[[3,4,1,2], [4,2,3,1]]); p\n", " Standard permutations of 5 avoiding [[3, 4, 1, 2], [4, 2, 3, 1]]\n", " sage: p.cardinality()\n", " 88\n", " sage: p.random_element().parent() is p\n", " True\n", "\u001b[31mInit docstring:\u001b[39m\n", " Base class for all parents.\n", "\n", " Parents are the Sage/mathematical analogues of container objects in\n", " computer science.\n", "\n", " INPUT:\n", "\n", " * \"base\" -- an algebraic structure considered to be the \"base\" of\n", " this parent (e.g. the base field for a vector space)\n", "\n", " * \"category\" -- a category or list/tuple of categories. The\n", " category in which this parent lies (or list or tuple thereof).\n", " Since categories support more general super-categories, this\n", " should be the most specific category possible. If category is a\n", " list or tuple, a \"JoinCategory\" is created out of them. If\n", " category is not specified, the category will be guessed (see\n", " \"CategoryObject\"), but will not be used to inherit parent's or\n", " element's code from this category.\n", "\n", " * \"names\" -- names of generators\n", "\n", " * \"normalize\" -- whether to standardize the names (remove\n", " punctuation, etc.)\n", "\n", " * \"facade\" -- a parent, or tuple thereof, or \"True\"\n", "\n", " If \"facade\" is specified, then \"Sets().Facade()\" is added to the\n", " categories of the parent. Furthermore, if \"facade\" is not \"True\",\n", " the internal attribute \"_facade_for\" is set accordingly for use by\n", " \"Sets.Facade.ParentMethods.facade_for()\".\n", "\n", " Internal invariants:\n", "\n", " * \"self._element_init_pass_parent == guess_pass_parent(self,\n", " self._element_constructor)\" Ensures that \"__call__()\" passes down\n", " the parent properly to \"_element_constructor()\". See\n", " https://github.com/sagemath/sage/issues/5979.\n", "\n", " Todo: Eventually, category should be \"Sets\" by default.\n", "\u001b[31mFile:\u001b[39m /home/conda/feedstock_root/build_artifacts/bld/rattler-build_sagelib_1780060433/work/src/sage/structure/parent.pyx\n", "\u001b[31mType:\u001b[39m ClasscallMetaclass\n", "\u001b[31mSubclasses:\u001b[39m Permutations_nk, Permutations_mset, Permutations_set, Arrangements, StandardPermutations_all, StandardPermutations_n_abstract, StandardPermutations_recoilsfiner, StandardPermutations_recoilsfatter, StandardPermutations_recoils, StandardPermutations_bruhat_smaller, ..." ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "Permutations?" ] }, { "cell_type": "code", "execution_count": 8, "id": "61877315", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2, 4, 1, 3]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Building a single permutation directly, in one-line notation\n", "p = Permutation([2, 4, 1, 3])\n", "p\n" ] }, { "cell_type": "code", "execution_count": 9, "id": "378d9ef8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "length (= number of inversions): 3\n", "descents: [2]\n", "cycle type: [4]\n", "is it a derangement? True\n", "inverse: [3, 1, 4, 2]\n" ] } ], "source": [ "# Some properties every permutation knows about itself\n", "print('length (= number of inversions):', p.length())\n", "print('descents:', p.descents())\n", "print('cycle type:', p.cycle_type())\n", "print('is it a derangement?', p.is_derangement())\n", "print('inverse:', p.inverse())\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "47c79302", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "there are 24 permutations of size 4\n" ] }, { "data": { "text/plain": [ "[(0, 1), (1, 11), (2, 11), (3, 1)]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The whole family of size n, and a classical statistic: descents\n", "n = 4\n", "Pn = Permutations(n)\n", "print('there are', Pn.cardinality(), 'permutations of size', n)\n", "\n", "# Count how many have exactly k descents (Eulerian numbers!)\n", "from collections import Counter\n", "counts = Counter(p.number_of_descents() for p in Pn)\n", "sorted(counts.items())\n" ] }, { "cell_type": "code", "execution_count": 11, "id": "4a939882", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[4, 1, 3, 2],\n", " [4, 2, 1, 3],\n", " [4, 2, 3, 1],\n", " [4, 3, 1, 2],\n", " [4, 3, 2, 1],\n", " [3, 4, 1, 2],\n", " [3, 4, 2, 1],\n", " [2, 4, 3, 1],\n", " [3, 2, 4, 1],\n", " [1, 4, 3, 2],\n", " [2, 1, 4, 3],\n", " [2, 4, 1, 3],\n", " [3, 1, 4, 2],\n", " [3, 2, 1, 4]]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Sage also has many *special* permutation families built in, e.g.:\n", "Permutations(4, avoiding=[1,2,3]).list() # permutations avoiding the pattern 123\n" ] }, { "cell_type": "code", "execution_count": 12, "id": "0879f677-50e3-4015-8c7f-bff74599fd36", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]\n" ] } ], "source": [ "# Let's count them using some python syntax\n", "seq = [Permutations(i, avoiding=[1,2,3]).cardinality() for i in range(10)]\n", "print(seq)" ] }, { "cell_type": "markdown", "id": "dfc9c5ca", "metadata": {}, "source": [ "## 3. Dyck words — and the Catalan numbers\n", "\n", "A **Dyck word** of semilength $n$ is a sequence of $n$ up-steps and $n$ down-steps (think `(` and `)`) that never goes below the axis. They are *the* prototypical example in analytic/enumerative combinatorics because they are counted by the **Catalan numbers**\n", "$$ C_n = \\frac{1}{n+1}\\binom{2n}{n}. $$\n", "\n", "In Sage the family is `DyckWords(n)`.\n" ] }, { "cell_type": "code", "execution_count": 136, "id": "71b80bbb", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Dyck words with 3 opening parentheses and 3 closing parentheses" ] }, "execution_count": 136, "metadata": {}, "output_type": "execute_result" } ], "source": [ "D = DyckWords(3)\n", "D\n" ] }, { "cell_type": "code", "execution_count": 15, "id": "5cc01f0e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "D.cardinality() # the 3rd Catalan number C_3 = 5\n" ] }, { "cell_type": "code", "execution_count": 16, "id": "12d6f890", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[1, 0, 1, 0, 1, 0],\n", " [1, 0, 1, 1, 0, 0],\n", " [1, 1, 0, 0, 1, 0],\n", " [1, 1, 0, 1, 0, 0],\n", " [1, 1, 1, 0, 0, 0]]" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "D.list() # all 5 Dyck words of semilength 3\n" ] }, { "cell_type": "code", "execution_count": 17, "id": "a626da5d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 1, 2, 5, 14, 42, 132, 429]" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# compare with the Catalan number function directly\n", "[catalan_number(n) for n in range(8)]\n" ] }, { "cell_type": "code", "execution_count": 139, "id": "3a14a43b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(())()\n", "as a lattice path of ups/downs: (0, 1, 2, 1, 0, 1, 0)\n", "area statistic: 1\n", "peak statistic: [1, 4]\n" ] } ], "source": [ "d = D.random_element()\n", "print(d)\n", "print('as a lattice path of ups/downs:', d.heights())\n", "print('area statistic:', d.area())\n", "print('peak statistic:', d.peaks())\n" ] }, { "cell_type": "markdown", "id": "b3cd2e3c", "metadata": {}, "source": [ "### Printing the *same* Dyck word in different styles\n", "\n", "One Dyck word can be displayed in many equivalent ways: as a string of letters, as a sequence of heights, or as an actual picture of the lattice path. Sage's `ascii_art` function is the generic tool for this last option — it works on Dyck words, trees, tableaux, partitions, and many other combinatorial objects, and is very presentation-friendly since it needs no graphics backend.\n" ] }, { "cell_type": "code", "execution_count": 150, "id": "4085356e", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "the word itself: (())()\n", "as a binary string (1 = up): [1, 1, 0, 0, 1, 0]\n", "as a sequence of heights: (0, 1, 2, 1, 0, 1, 0)\n" ] }, { "data": { "image/svg+xml": [ " " ], "text/plain": [ "[1, 1, 0, 0, 1, 0]" ] }, "execution_count": 150, "metadata": {}, "output_type": "execute_result" } ], "source": [ "d = DyckWords(3)[2] # fix one concrete example so all the printouts below refer to the same object\n", "print('the word itself: ', d)\n", "print('as a binary string (1 = up): ', list(d))\n", "print('as a sequence of heights: ', d.heights())\n", "d\n" ] }, { "cell_type": "code", "execution_count": 51, "id": "31036623", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " /\\ \n", "/ \\/\\" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ascii_art draws it as an actual mountain-range / lattice path picture\n", "ascii_art(d)\n" ] }, { "cell_type": "code", "execution_count": 52, "id": "f1e79759", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ /\\ ]\n", "[ /\\ /\\ /\\/\\ / \\ ]\n", "[ /\\/\\/\\, /\\/ \\, / \\/\\, / \\, / \\ ]" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ascii_art also happily lays out several objects side by side --\n", "# handy for showing *all* Dyck words of a given size at a glance\n", "ascii_art(DyckWords(3).list())\n" ] }, { "cell_type": "code", "execution_count": 57, "id": "b57ec7c7-07f6-4669-8ee9-dd8b4da583cb", "metadata": {}, "outputs": [], "source": [ "# D.options.ascii_art?\n", "D.options.ascii_art = 'pretty_print'" ] }, { "cell_type": "code", "execution_count": 59, "id": "e148f68a-64bb-4451-b617-4440620e0200", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " _\n", " ___| \n", "| x .\n", "| . ." ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# after changing the options, the picture changes\n", "ascii_art(d)" ] }, { "cell_type": "code", "execution_count": 61, "id": "b12781fe-84f3-4972-85f9-8be6bead0a17", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ _ ___ _ ___ _____ ]\n", "[ _| | x ___| _| x | x x ]\n", "[ _| . _| . | x . | x . | x . ]\n", "[ | . ., | . ., | . ., | . ., | . . ]" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# different pictures than above with different options\n", "ascii_art(DyckWords(3).list())" ] }, { "cell_type": "markdown", "id": "0bcc16fc", "metadata": {}, "source": [ "### From Dyck words to trees, and back\n", "\n", "Dyck words are also a great excuse to show **bijections**: Sage can turn a Dyck word into an ordered/binary tree and back.\n" ] }, { "cell_type": "code", "execution_count": 109, "id": "cd0bff3d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[., .], [., .]]" ] }, "execution_count": 109, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t = d.to_binary_tree()\n", "t\n" ] }, { "cell_type": "code", "execution_count": 111, "id": "126f3ebd", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " o\n", " / \\\n", "o o" ] }, "execution_count": 111, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# the same tree, drawn with ascii_art instead of the default text repr\n", "ascii_art(t)\n" ] }, { "cell_type": "code", "execution_count": 112, "id": "90f179a1", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 112, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ... and back again:\n", "t.to_dyck_word() == d\n" ] }, { "cell_type": "markdown", "id": "7b5ef136", "metadata": {}, "source": [ "## 4. Binary trees\n", "\n", "`BinaryTrees(n)` is the family of binary trees with $n$ internal nodes. \n" ] }, { "cell_type": "code", "execution_count": 65, "id": "f980d26b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "cardinality: 5\n" ] }, { "data": { "text/plain": [ "[[., [., [., .]]],\n", " [., [[., .], .]],\n", " [[., .], [., .]],\n", " [[., [., .]], .],\n", " [[[., .], .], .]]" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "BT = BinaryTrees(3)\n", "print('cardinality:', BT.cardinality()) # again C_3 = 5\n", "BT.list()\n" ] }, { "cell_type": "code", "execution_count": 66, "id": "1a5da136", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[., [., [., .]]]" ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The default (compact, nested) text representation of one tree\n", "t = BT.random_element()\n", "t\n" ] }, { "cell_type": "code", "execution_count": 67, "id": "847c3f1d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "o\n", " \\\n", " o\n", " \\\n", " o" ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The SAME tree, drawn as actual ascii art -- much easier to read out loud in a talk\n", "ascii_art(t)\n" ] }, { "cell_type": "code", "execution_count": 68, "id": "935d222f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ o , o , o , o, o ]\n", "[ \\ \\ / \\ / / ]\n", "[ o o o o o o ]\n", "[ \\ / \\ / ]\n", "[ o o o o ]" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# ascii_art also lines up a whole family of trees side by side\n", "ascii_art(BinaryTrees(3).list())\n" ] }, { "cell_type": "code", "execution_count": 69, "id": "21c12ee3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "number of nodes: 3\n", "depth: 3\n" ] } ], "source": [ "# A tree knows about itself, just like every other combinatorial object:\n", "print('number of nodes:', t.node_number())\n", "print('depth:', t.depth())\n" ] }, { "cell_type": "code", "execution_count": 73, "id": "dbc6f4eb", "metadata": {}, "outputs": [ { "data": { "text/plain": [ " _\n", " _| \n", " _| .\n", "| . ." ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Round trip: tree -> Dyck word -> tree\n", "w = t.to_dyck_word()\n", "ascii_art(w)\n" ] }, { "cell_type": "code", "execution_count": 74, "id": "bd0344c8", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 74, "metadata": {}, "output_type": "execute_result" } ], "source": [ "w.to_binary_tree() == t\n" ] }, { "cell_type": "markdown", "id": "87362153", "metadata": {}, "source": [ "**Take-away:** `ascii_art` is not specific to Dyck words or trees — try it on almost *any* combinatorial object in Sage (`Partitions`, `Tableaux`, `SetPartitions`, ...) whenever the default `print`/`repr` output looks too flat. It is purely text-based, so it works equally well in a terminal, in this notebook, or projected on a screen.\n" ] }, { "cell_type": "code", "execution_count": 159, "id": "e7691823-60da-4d4b-a67f-e0b293e81ead", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[[[., [., .]], .], [., .]], [[., .], [[., .], .]]]\n", " __o___\n", " / \\\n", " o _o_\n", " / \\ / \\\n", " o o o o\n", " / /\n", "o o\n", " \\ \n", " o \n", "6[4[3[1[., 2[., .]], .], 5[., .]], 8[7[., .], 10[9[., .], .]]]\n" ] }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAASsAAAGDCAYAAABz6zY3AAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjExLjAsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvlcelbwAAAAlwSFlzAAAPYQAAD2EBqD+naQAAJBlJREFUeJzt3QtYVVXCPvAXNFHx1kXNW1pCOYGeAisgS1H7LEsbJ2sSsQYELcQuY9mUYzOTfV0oqy/NDEVIGSzLsqy++LyAhkAXGEGwEjR1SkvNOyoInP+zVv/NcDkHzjmcc9hr7/f3PI1x2Ht7WKxeXvZee4+P1Wq1gohI53zb+g0QETmCYUVESmBYEZESGFZEpASGFblVbW0tR5Q8gmFFrVJYWIjZs2djeGgoOnbsiHbt2sk/xcfidfF5Infw4dIFckV5eTlmxMcjKzsb/Xr1xNjhFlgCB6Obf2ecrDiDorLd2PhNEX46dBiRo0YhedkyBAQEcLDJZQwrclpGRgbi4uLQ56IL8VLidEwYEYb27ds12a66ugbrc/Lx+OIUHDx6DCkpKZgyZQpHnFzCsCKngyo6OhrR40ZjydzZ8O/Use5zP/96FLt/PIghgwbg4u7d6l6vOHsOCUmLkJ65Genp6YiKiuKok9MYVuSwsrIyWCwWTB4ZgdT5c+Dr+9spzzPnzmHG8/+Dj77IwzWBV+DAkaOYOel2zI2+u8GJ95gFC/H+llwUFxfzV0JyGsOKHDY6MhL7y3dh+8olDRrVvX99DkVle7D5jRfR55KLUVNTg39mZuG+8WMb7C8almVaAgYGXonNWVkceXIKrwaSQwoKCuTJ9KRZ0xsE1bd792PNpq1ISoyTQSWIK4KNg0oQ+yUlxsrj8CohOYthRQ5JS0tD/9695Mn0+rIKitC+XTvccn2IDK6vSr/HidMVdo8zcUS4vHqYmprKkSentHduczKrvNxcjAkd1uSq38EjR3FRt66Y9o8k7Nj9A7p27oydP+zH09On4olp9zQ5jth/TKgF+Xl5Xnz3ZARsVuSQktJSuY6qsQvat8ehY8cROKAfvns3BV+nLsLqBX/Bk0tWYFtRqc1jWQKvwI6SEo48OYVhRS0SV/IqKyvlgs/GLu/bW/4Ze8e4utcm3hQuly7k7thp83jdu/jL4/HWHHIGw4paniS+vvDz85Mr0xsT56rEOat9P/9S99qxk6fkeaveF11o83jic+J42tIHIkfwnBU5JDgoSN5C09ilF18kz03FP/8a5sdORdfOnfD6mnUI6N8Xd0WOsHksscxhaHAwR56cwrAih4RHRODDNe/KW2gan2RfMPN+/G7QZVi3ZRtqrVbcGnYdEu+e0GCJg0bsv6mgCJPu+SNHnpzCRaHkELEuKjQ0FGufn49Jo250edQ+yM7B5Cefleu2QkJCOPrkMIYVObWCfV/ZLhStariC3VFcwU6twTOc5DDxmJefDh/BAy++7vSVPLH9g0mL5NMXxHGInMWwIodt2bIFlVVVyPi/LHlTsmhKjhDb/WnBy0j/fBNiYmJ4EzO5hGFFDhHPohLPsEpISMCqVavk0xPETcniHJQ4aW6LeF18Xmy3dkseRo4ciTfffFM+JobIWbwaSE4F1eLFi+Hj44MbbrhBPilUnCwX9/qJW2jEynSx4FOsoxLLE8RVP/GkUHGuKzM5GVdccQXi4+Nx3333yeOK52IROUw81pjInuXLl4v/x25rQkKCtba2tsnnCwoKrImJidbhoaFWPz8/ua34U3wsXhefr6+mpsYaGxtr9fHxsa5atYoDTw5jWJHLQWWLCCNHtmFgkbP4ayA5/KufIxy5hUZss+z/XxHkr4TkKIYVuS2onMHAImcxrMjrQaVhYJEzGFbUJkGlYWCRoxhW1GZBpWFgkSMYVtSmQaVhYFFLGFYmp4eg0jCwqDkMKxPTU1BpGFhkD8PKpPQYVBoGFtnCsDIhPQeVhoFFjTGsTEaFoNIwsKg+hpWJqBRUGgYWaRhWJqFiUGkYWCQwrExA5aDSMLCIYWVwRggqDQPL3BhWBmakoNIwsMyLYWVQRgwqDQPLnBhWBmTkoNIwsMyHYWUwZggqDQPLXBhWBmKmoNIwsMyDYWUQZgwqDQPLHBhWBmDmoNIwsIyPYaU4BtV/MLCMjWGlMAZVUwws42JYKYpBZR8Dy5gYVgpiULWMgWU8DCvFMKgcx8AyFoaVQhhUzmNgGQfDShEMKtcxsIyBYaUABlXrMbDUx7DSOQaV+zCw1Maw0jEGlfsxsNTFsNIpBpXnMLDUxLDSIQaV5zGw1MOw0hkGlfcwsNTCsNIRBpX3MbDUwbDSCQZV22FgqYFhpQMMqrbHwNI/hlUbY1DpBwNL3xhWbYhBpT8MLP1iWLURBpV+MbD0iWHVBhhU+sfA0h+GlZcxqNTBwNIXhpUXMajUw8DSD4aVlzCo1MXA0geGlRcwqNTHwGp7DCsPY1AZBwOrbTGsPIhBZTwMrLbDsPIQBpVxMbDaBsPKAxhUxsfA8j6GlZsxqMyDgeVdDCs3YlCZDwPLexhWbsKgMi8GlncwrNyAQUUMLM9jWLUSg4o0DCzPYli1AoOKGmNgeQ7DykUMKrKHgeUZDCsXMKioJQws92NYOYlBRY5iYLkXw8oJDCpyFgPLfRhWDmJQkasYWO7BsHIAg4pai4HVegyrFjCoyF0YWK3DsGoGg4rcjYHlOoaVHQwq8hQGlmsYVjYwqMjTGFjOM11Y1dbWyoliD4OK9BxYtS3MX0OzGlxBQYE1MTHRGhoSYvXz87OKL1n8KT4Wr4vPa5YvXy4/n5CQYK2trW3T903mUVNTY42NjbX6+PhYV61a5fL8NTof8T8woPLycsyIj0dWdjb69eqJscMtsAQORjf/zjhZcQZFZbux8Zsi/HToMCJHjcLYW27BvHnzkJCQgMWLF8PHx6etvwQyEdGY4uPjkZqaipUrVyIsLMyp+Zu8bBkCAgJgZIYMq4yMDMTFxaHPRRfipcTpmDAiDO3bt2uyXXV1Ddbn5GPOomXY//MvGDNmLDIzMxlU1KaBtWLFCvh16IB+PS9xaP4+vjgFB48ek6cwpkyZAqPyNWJQid/7J4+MQNGqJZg06sa6b3Rm/jcYOnUmZr20WH4sXhef35G+FFH/NRobN27E6tWr2/grILMS56IiIyPlD8vJkSPq5q8o+W+8/zFue2Qero+djT888QzWf5FfN3/FdmK+T506Vc5/ozJUsyorK4PFYpHfuNT5cxqciPz516MIi3sEXTt3wqBLe2P9wmea/FSLWbAQ72/JRXFxseErNel3/t41MgJp9ebvE2+kYMX6TLz+5wcROKAfsgqK8OSbqXjvv+fJsDLL/DVUWI2OjMT+8l3YvnIJ/Dt1rHtdfInjHn4Kt4Vfh9wdO3GusqpJWAkVZ8/BMi0BAwOvxOasLC+/ezI7e/N32NQHcMsNIVj40Iy6126MfxRBgwch+S8Pm2b+GubXwIKCAnkyMmnW9AbfaOGFle/Kav3IvZOaPYbYLykxVh6nsLDQw++YyLH5GzHsauQW75RhJOw9+DO+3/8jbrIEmWr+Gias0tLS0L93L3kysr68HTvx+pqPkPrXOQ6dOJ84IlxefRFXZYjaev4Ki+Yk4OrLL0OfO6YgcHIMgqNm4m9x0Zh221hTzV/DLArNy83FmNBhDa6aHD91GlP/9iKWPJ6Ivj0vdug4Yv8xoRbk5+V58N0StTx/Na+98yE+2fYl3nhsFq66bAC2/KsYf136NoIuH4jRw68xzfw1TLMqKS2V61Dqyy/5Dj8eOoKnl62UVwHFPxu+KsTW7SXy33848LPNY1kCr8COkhIvvXMi2/NXqDp/Xs7fp2OnyiZ1fdBVeDz6bky86QY8nbzSVPPXEM1KXAmprKyUC+bqG2EJQuHbbzR4bc7ryaisOo/Fj81CPzttq3sXf3k8U9/aQG0+f4Wq89Xyn0t6dG/w+iU9eqCo7AdTzV9DhJX4hvj5+cmVvfV16dwJwYMHNXhNTIhz7auavF7fidMV8nhG+kaTevNXm8PX/e5KvLn2E9waNlwG0Z6fDuLdjdm4e8zNppq/hvlqgoOC5C0I7lBUtgdDg4Pdciyi1s7fVX+fi1prLfreEYWAyTG4esoMRIZY8N8z/2Sq+WuIZiWER0TgwzXvylsQbJ2k1Lzy8Ey57soesf+mgiJMuuePHnqnRM7NX7EQdOvShThZUYHDx07I23A6+nUw3fw1TLOKiYmRN3WKe6WaM6B3T1x2aS+7n/84J08eRxyPSE/zt5u/Pwb372s3qIw+fw23gn1f2S55r1TjhXWOMPoKYNI3zl+TNCtBPCZD3H2ekLRIXglxhthe7Cf2F8ch8jbOXxOFlbh5UzwmIz1zM/60YGHd7QktEduJm0DFfmJ/I94ESmrNXzEfOX8N/GugRjwm4/7770O/Sy7GwodnyFsQ7D0PSPyOP3fxClM8D4jUeh5br+5dHZq/c15fhkPHTxp+/hoyrL788kv5pMWgoKtRWrpT3islbkEQK3vFOhWxDkVc3t34zXYcOHwE115zDda89x4bFenG0qVLkThrFmpqa+3O300Fvz0ptJ2vLz5ctw4TJkyAkRkyrMaPH4+9e/dix44dKCoqkjd1inulxC0IYmWvWDAn1qHcEBaGrVu3okuXLti2bRufEEq6IP6TDAkJQY8ePbBw4UK78zcsPBzTpk1DVFSUfA7W2rVrYWhWg8nPz5cP1V+9erXdh/PX9/nnn8vtMzMzvfQOiZq3bt06OSezsrJanL9Camqq3H779u1WIzNcs6rfqtq1s784VCO+/IiICNmq2K5IT60qy8HlM9XV1RgyZIjx25XVRK3KHrYrUqFVNccM7cpQzcrZVqVhuyJVW5Wp2pXV5K1Kw3ZFqrYqs7QrwzQrV1uVhu2KVG1VpmlXVgNobavSsF2Rqq3KDO3KEM2qta1Kw3ZFqrYqU7Qrq+Lc1ao0bFekaqsyertSvlm5q1Vp2K5I1VZl+HZlVZi7W5WG7YpUbVVGbldKNyt3tyoN2xWp2qoM3a6sivJUq9KwXZGqrcqo7UrZZuWpVqVhuyJVW5Vh25VVQZ5uVRq2K1K1VRmxXSnZrDzdqjRsV6RqqzJku7IqxlutSsN2Raq2KqO1K+WalbdalYbtilRtVYZrV1aFeLtVadiuSNVWZaR2pVSz8nar0rBdkaqtylDtyqqItmpVGrYrUrVVGaVdKdOs2qpVadiuSNVWZZh2ZVVAW7cqDdsVqdqqjNCulGhWbd2qNGxXpGqrMkS7suqcXlqVhu2KVG1Vqrcr3TcrvbQqDdsVqdqqlG9XVh3TW6vSsF2Rqq1K5Xal62alt1alYbsiVVuV0u3KqlN6bVUatitStVWp2q5026z02qo0bFekaqtStl1ZdUjvrUrDdkWqtioV25Uum5XeW5WG7YpUbVVKtiurzqjSqjRsV6Rqq1KtXemuWanSqjRsV6Rqq1KuXVl1RLVWpWG7IlVblUrtSlfNSrVWpWG7IlVblVLtyqoTqrYqDdsVqdqqVGlXumlWqrYqDduVuancqpRpV1YdUL1VadiuzEv1VqVCu9JFs1K9VWnYrszJCK1KiXbV1mlplFalYbsyH6O0Kr23qzZvVkZpVRq2K3MxUqvSfbtqy6Q0WqvSsF2Zh9FalZ7bVZs2K6O1Kg3blTkYsVXpul21VUoatVVp2K6Mz6itSq/tqs2alVFblYbtytiM3Kp0267aIiGN3qo0bFfGZfRWpcd21SbNyuitSsN2ZUxmaFW6bFfeTkeztCoN25XxmKVV6a1deb1ZmaVVadiujMVMrUp37cqbyWi2VqVhuzIOs7UqPbUrrzYrs7UqDduVMZixVemqXXkrFc3aqjRsV+oza6vSS7vyWrMya6vSsF2pzcytSjftyhuJaPZWpWG7UpfZW5Ue2pVXmpXZW5WG7UpNbFU6aVeeTkO2qobYrtTDVqWPduXxZsVW1eSHAyIiIuDj44Nt27bJP0m/2Kp01K48mYRsVbaxXamDrUo/7cqjzYqtyu4PCLYrBbBV6axdeSoF2aqax3alf2xV+mpXHmtWbFUt/pBgu9IxtiodtitPJCBblWPYrvSLrUp/7cojzYqtyuEfFGxXOsRWpdN25e70Y6tyDtuV/rBV6bNdub1ZsVU5/cOC7UpH2Kp03K5ak3Q1NTUNPmarcn+7ajzG5F6Nx5etyv3tyl1z2KlmVVhYiNTUVOTl5qKktBSVlZXw8/NDcFAQwiMi5OePHTtm+nsAW9OuFi1ahLS0NLtjHBMTI+/+J9c0N4fDwsOxYcMG9O3b17RPVnBHu5o3b16zOeHqHHYorMrLyzEjPh5Z2dno16snxg63wBI4GN38O+NkxRkUle3Ghq+348DhIwgKuhrr1n2EgIAAV79uUxLf3Pi4ONTU1tod443fFOGnQ4cROWoUkpct4xg7wbE5/C8cOPwrrr32GqxZ8x7H10kvvvgi5j31lMfmcIthlZGRgbi4OPS56EK8lDgdE0aEoX37pk9OqK6uwfqcfDy+OAUHjx5DSkoKpkyZ4uzXa0raGPfq3hWvPDyTY+yh8eUc9vwY9+zeFa96aA43G1biDURHRyN63GgsmTsb/p06ytePnTyF/NLvUHW+GsMCLsflfS+t26fi7DkkJC1CeuZmpKenIyoqyrWv3iQaj/GZc+fwae5XTbYT3/yLu3eT/84xdn18a2trsTY7x+a2YUG/w5BBAzi+Lozx1KlTERliwT1jb8aM34+3eYP+qYozyC4sxrmqKoRcFYBnUv7pVE7YDauysjL5++fkkRFInT8Hvr6+8vXn334Hyes+kyEl6p74y+8bfwveeGxW3RsUEyJmwUK8vyUXxcXFrNN22Brj/JJvERH/KKaOi0T7es/++ltcNAb1+c8PBY6xa+N76OhxPPHG8gbb7fv5kJzH61/+B26/8QaOr5NjHBQUhA7t2mFA7574bt+/UfXFp01aVeH3ZRj/6Hy5TY8u/sgr+RZL5z6EDV8VOpwTdsNqdGQk9pfvwvaVS+oalfDR1jzcFj4cHS64QH6cU1SCmx94DFuXvowRluC67cRPf8u0BAwMvBKbebISjo6xFlYnN32ILp07NfvN4xg3z94cbuzBpEVY/0U+9q1b2eDhkBxfx8a4pGg7cpYuRMH3ZYh6+gWbYTV06kwMG3w5/vnMX+THr6xei6eTV6Lkn29h7ENPOZQTv9WlRgoKCuSJyKRZ05t8k++8ObwuqISBl/aWf56rrGqwndgvKTFWHkdcgSHHx1jI/LIA72/+AqV79todOo6x6+OrOXuuEu9syEbMHf/V5Cm2HF/Hxnjp3NkIvKyf3e2Ky/egdM8+zL7nzrrXZv7+dtTWWuVFDUdzwmZYiUvn/Xv3kudJbNnz00Gkffp/eHX1B/j93L9j+sRbMea6a5tsN3FEuLwqIK50keNjLH4YLFm7Hm9/ugHh8Y/izsf/Js9l2cIxtq2lOax5P+sLeaVq+sRxHF8PjXHJ7n3yz6DLBzb4QTCoT2+U7Nnr8Bxub+tFsT5iTOgwm2fzhV+OHsOWwmL8cvQ4fj56DAH9+9o8oSb2HxNqQX5eXrNvwozsjXHfSy6W1ThgQF/58f6fD+G62NmYn7wSCx+a0eQ4HGPnxrexFeszccv11zY4H8jxde8Yn6ioQLt2vujq37nB6xd164qTpyscnsM2m5VYyCXWR9gTPvRqpM5/DJ+9+iw+efkZ+bvne5u22tzWEngFdpSUNPsmzMjeGF92aa+6oNI+vu+2sfhsW9MrhBqOsePjW1/5vw9g6/YSxE28rdntOL6uj7HQya8Dampqm5wqOnXmDDr6+Tk8xk3CSlxlEitOxUIuR1x7VQACB/SVZ/dt6d7FXx5PHJdcG+POHTvi15On7H6eY+zaHF7xSSZ69uguz8M2h+Pbujk8uN9vP3z3Hvyl7rWamhr8eOgIBvfr4/AYNwkrcXlXLI0Xv8c3Js6bHD1xqsmvhOJNaCfaGztxukIeT1v6QM2Psfi1r77z1dX4aGsuwoKG2B06jrHjc7j+fywrP9uI+8aPxQXtbZ4N4fi2cow1YcFDcEmP7nh305a61z7P/wbHT1fg9huvd3gO2/wuiXt4xNL4xsSl3FEJc3HL9SG4amB/HD52Am9/tkGeOIubeKvNv6CobA+GBv9nSQM1P8ZvfvAJtu/ajcjh18DXx0deqTpy/CRWL3jS7tBxjB2fw5rPcr/GgSO/2p23HF/Hxzi3eCd2/ftHfFn6vXx95f9uhK+vD8bdEIo+l1wsfxi8+shMxD77Ck5VnMWF3brgtXc+xKzJE/C7QZc5PIdtxpi42VDcwyOWxtfX88IeyF/+GoYMHICS3XtRef68POmbt/w1m5eHxf6bCorkDaLk2Bg/nxCLJ++/F8dPncZPh3+Vq4G/X5NS903lGLdufDWHj5/AU3+6F1de1r/Z43AOtzzG3/6wX15wO1dZifvHj8UX23fIj4+dOl237dRxo5G9JAm11lp5/+XSJx7C639OcGqMbS4KFesdQkNDsfb5+Zg06ka46oPsHEx+8lm5HoNPCuAYexPnsPHGuNkV7PvKdqFoVfOrf+3h6t+WcYw9i+NrrDG2ezZLPL5B3BUtbkp29kqe2F7sJ/YXxyGOcVvgHDbWGNsNK3FToXh8g7grWtyULBLQEWI7sb3YT+zP51rZxzH2LI6vscbYqedZiXt4xNJ4e8+p+TgnD3MXr+DzrJzEMfYsjq8xxtilJ4WKpfFixalYyCXWR4jLjuJsvngCoPgd9q3kZDYqJ3GMPYvjq/4Yu/QMdnEPT/GOHaiqqkKHDh0wbOhQedmRzwdvvfpjLG4/0J5fLdagcIw5virwVE64/H/FpV225LIEzxInIbn6n+OrKnfmBO+B0TkGFceXfsOwIiIlMKyISAkMKyJSAsOKiJTAsCIiJTCsiEgJDCsiUgLDioiUwLAiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAkMKyJSAsOKiJTAsCIiJTCsiEgJDCsiUgLDioiUwLAiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAkMKyJSAsOKiJTAsCIiJTCsiEgJDCsiUgLDioiUwLAiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAkMKyJSAsOKiJTAsCIiJTCsiEgJDCsiUgLDioiUwLAiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAkMKyJSAsOKiJTAsCIiJTCsiEgJDCsiUgLDioiUwLAiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAkMKyJSAsOKiJTAsCIiJfhYrVaroxsXFhYiNTUVebm52FFSgqqqKnTo0AFDg4MRHhGBmJgYhISEePYdE5GueSonHAqr8vJyzIiPR1Z2Nvr16omxwy2wBA5GN//OOFlxBkVlu7HxmyL8dOgwIkeNQvKyZQgICHD1ayUiBZV7OCdaDKuMjAzExcWhz0UX4qXE6ZgwIgzt27drsl11dQ3W5+Tj8cUpOHj0GFJSUjBlyhTXvmoiUkqGF3Ki2bASbyA6OhrR40ZjydzZ8O/UscUDVpw9h4SkRUjP3Iz09HRERUU59EaISE0ZXsoJu2FVVlYGi8WCySMjkDp/Dnx9fev+ktUbspC87jP8cOAXfLF0IYYMGtBg39raWsQsWIj3t+SiuLiYvxISGVSZjZwQ//0v++h/kfbpBvx46AgG9+uD+bFRGHPdta3KCbthNToyEvvLd2H7yiUNknLGC/8j/5KIoVcj7rlXUZy+FMGDBzXZX4SaZVoCBgZeic1ZWa6PBhHplq2ceP7td/DiqjVY8dc/Y/iQK7Hx639h9sIl2PzGi7ghaIjLOWFz6UJBQYE8SZY0a3qTSvfWEw9h+VOPIuSq5lNQ7JeUGCuPI64OEJGxFNjJiRXrM/HAH+7AH0aNwGWX9kLshHGYeFMYnktb3aqcsBlWaWlp6N+7lzxJ1piPj4/DX8zEEeHyqoC4jElExpJmJyfOVZ1HZz+/Bq918vPD1u0lrcoJm2El1keMCR1m82y+M8T+Y0ItyM/La9VxiEh/7OXE7Tdej5T1n+O7vf+WH+eXfIu1WTk4cbpC/trnak7YDKuS0lK5PsIdLIFXyIVhRGQsJXZy4qXEONxyfQiui50N/1F3IvbZV/DgXXfIz9lbfOBITjQJK3HyvLKyUi7kcofuXfzl8cRxicgYapvJia7+neV57VOb1+GXz97BzneWwe+CC3Bx927o0rmTyznRJKzEpUc/Pz+54tQdRPUTx9OWPhCR+nwdzAkRTqJNfZCdg9sjrm9VTtj8THBQkFwa7w5FZXvkPUFEZCzBdnIiu7AIGZlZqDp/HqfPnMXDr76JA4d/xd/jo1uVEzbDStxsKO7hEUvjG1uydj163noPRic+IT+++cHH5McpH3/eZFux/6aCIoSFhzf7JohIPeF2ckIsaxJrq3qPvxeX3HoPdu7Zjy1vvoxBfS61eRxHc8LmolCx3iE0NBRrn5+PSaNubPC5s+cqUXGu6Rn9Lp06oaNfhwavieo3+cln5XoMPo2ByFgKm8kJQTQrocMFFzR7HEdzotkV7PvKdqFoVcMV7I7iCnYi4xvtxZywezZLPL5B3BUtbjZ09kqe2F7sJ/YXxyEiY0r2Yk7YDStxU6F4fIO4K1rcbGhrMZctYjuxvdhP7M/nWhEZV4AXc8Kp51mJe3jE0nh7z6n5OCcPcxev4POsiEwmwws54dKTQsXSeLHiVCzkEusjxGVHcTZfPAFQ/A77VnIyGxWRyZR7OCdcega7uIeneMeOumcrDxs6VF525DPYiaiwXk6IW2jEynSx4FOso2pNTjgVVrYuW3JZAhG1dCLdHXew8B4YIvIod91qx7AiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAkMKyJSAsOKiJTAsCIiJTCsiEgJDCsiUgLDioiUwLAiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAkMKyJSAsOKiJTAsCIiJTCsiEgJDCsiUgLDioiUwLAiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAkMKyJSAsOKiJTAsCIiJTCsiEgJDCsiUgLDioiUwLAiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAkMKyJSAsOKiJTAsCIiJTCsiEgJDCsiUgLDioiUwLAiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAkMKyJSAsOKiJTAsCIiJTCsiEgJDCsiUgLDioiUwLAiIiUwrIhICQwrIlICw4qIlMCwIiIlMKyISAk+VqvV6ujGhYWFSE1NRV5uLnaUlKCqqgodOnTA0OBghEdEICYmBiEhIZ59x0RkSg6FVXl5OWbExyMrOxv9evXE2OEWWAIHo5t/Z5ysOIOist3Y+E0Rfjp0GJGjRiF52TIEBAR45ysgIlNoMawyMjIQFxeHPhddiJcSp2PCiDC0b9+uyXbV1TVYn5OPxxen4ODRY0hJScGUKVM8+d6JyESaDSsRVNHR0YgeNxpL5s6Gf6eO8vXC78vwVekudO7oh5uuCcblfS+t26fi7DkkJC1CeuZmpKenIyoqyjtfCRGZM6zKyspgsVgweWQEUufPga+vrwyiO+bMx+mz5xA6JBDHTp7C+pwv8WLidMy++866fWtraxGzYCHe35KL4uJi/kpIRJ4Lq9GRkdhfvgvbVy6pa1Snz5zFv3btlm1K89aHnyJx4Rs4sD4DPS/sUfe6CDbLtAQMDLwSm7OyWv9OicjUbC5dKCgokCfTk2ZNrwsqoUvnTg2CShhhCUJNTS32Hvylwetiv6TEWHkccRWRiMjtYZWWlob+vXvJk+kteT8rR4bY1ZcPbPK5iSPC5dVDsdyBiMjtYSXWUY0JHWbzql992YVFeC7tHbyQENuggWnE/mNCLcjPy2vVmyQishlWJaWlch1Vc74s/Q53Pv4PzIm6Cwl3TbC7nSXwCrmAlIjIrWElruRVVlbKBZ/2fFX6PcY9/BQevOsOPPdgTLN/Qfcu/vJ44rhERG4LK7FEwc/PT65Mt+Xrnd9j3CNP4YE/3CF//WvJidMV8njiuERErmpv68XgoCB5C01jh48dx62PzEOPLv7ynxdWvlv3ubsiRyBwQL8m+xSV7ZH3DhIRuT2sxE3JH655V95C0/gke/zvx8s/j5+uaPD6+erqJscR+28qKMKke/7YqjdJRGRzUahYFxUaGoq1z8/HpFE3ujxKH2TnYPKTz8p1W3waAxF5bAX7vrJdKFr1nxXszuAKdiJyJ7tnvcVjXsTTE8RNyc5eyRPbi/3E/uI4REQeCyvxPCrxmBfx9ARxU7JoSo4Q24ntxX5ifz7Xioi8/jwrca+fuIXG3vOsPs7Jw9zFK/g8KyLSx5NCxS00YmW6WPAp1lGJ5Qniqp94Uqg41/VWcjIbFRG1/TPYxb1+4hYasTJdLPgU66jCwsP5DHYi0kdY2TqRzpXpRKT7sCIi8hbesEdESmBYEZESGFZEpASGFRFBBf8PhIzQDyDYdFsAAAAASUVORK5CYII=", "text/plain": [ "Graphics object consisting of 20 graphics primitives" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "B = BinaryTrees(10)\n", "tree = B.random_element()\n", "print(tree)\n", "print(ascii_art(tree))\n", "\n", "# Convert the combinatorial tree into a proper, plottable Graph\n", "ct = tree.canonical_labelling()\n", "print(ct)\n", "\n", "# Convert the LABELLED tree to a graph -> vertices are now distinct labels\n", "G = ct.to_undirected_graph()\n", "\n", "# Root of the labelled tree (its label) so the tree layout knows where to start\n", "root_label = ct.label()\n", "\n", "G.show(layout='tree', tree_root=root_label)" ] }, { "cell_type": "markdown", "id": "a1c4c1b1", "metadata": {}, "source": [ "## 5. Compositions\n", "\n", "A **composition** of $n$ is a way of writing $n$ as an ordered sum of positive integers, e.g. $4 = 1+1+2 = 2+1+1 = \\dots$ (order matters, unlike partitions below).\n" ] }, { "cell_type": "code", "execution_count": 75, "id": "8516a086", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "number of compositions of 4: 8\n" ] }, { "data": { "text/plain": [ "[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "C = Compositions(4)\n", "print('number of compositions of 4:', C.cardinality()) # 2^(n-1)\n", "C.list()\n" ] }, { "cell_type": "code", "execution_count": 76, "id": "f44a6dfd", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 3, 2]\n", "sum: 6\n", "number of parts: 3\n" ] } ], "source": [ "c = Composition([1, 3, 2])\n", "print(c)\n", "print('sum:', c.size())\n", "print('number of parts:', len(c))\n" ] }, { "cell_type": "markdown", "id": "3c149805", "metadata": {}, "source": [ "## 6. Partitions\n", "\n", "A **partition** of $n$ is like a composition but *unordered* — only the multiset of parts matters. These are ubiquitous (representation theory, symmetric functions, ...).\n" ] }, { "cell_type": "code", "execution_count": 77, "id": "2934ab3c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "p(6) = 11\n" ] }, { "data": { "text/plain": [ "[[6], [5, 1], [4, 2], [4, 1, 1], [3, 3], [3, 2, 1], [3, 1, 1, 1], [2, 2, 2]]" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Pt = Partitions(6)\n", "print('p(6) =', Pt.cardinality())\n", "Pt.list()[:8] # just show the first 8\n" ] }, { "cell_type": "code", "execution_count": 79, "id": "185398d4", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[3, 3, 2, 1]\n", "conjugate partition: [4, 3, 2]\n", "***\n", "***\n", "**\n", "*\n" ] } ], "source": [ "la = Partition([3, 3, 2, 1])\n", "print(la)\n", "print('conjugate partition:', la.conjugate())\n", "print(la.ferrers_diagram())\n" ] }, { "cell_type": "markdown", "id": "2b0aebd3", "metadata": {}, "source": [ "## 7. Set partitions\n", "\n", "A **set partition** splits a finite set into non-empty, unordered, disjoint blocks. These are counted by the **Bell numbers**.\n" ] }, { "cell_type": "code", "execution_count": 81, "id": "5a426ff8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Bell number B_4 = 15\n" ] }, { "data": { "text/plain": [ "[{{1, 2, 3, 4}},\n", " {{1, 2, 3}, {4}},\n", " {{1, 2, 4}, {3}},\n", " {{1, 2}, {3, 4}},\n", " {{1, 2}, {3}, {4}},\n", " {{1, 3, 4}, {2}}]" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" } ], "source": [ "SP = SetPartitions(4)\n", "print('Bell number B_4 =', SP.cardinality())\n", "SP.list()[:6] # just show the first 6\n" ] }, { "cell_type": "code", "execution_count": 83, "id": "8ce7285b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{{1, 4}, {2}, {3}}\n", "number of blocks: 3\n" ] } ], "source": [ "sp = SetPartitions(4).random_element()\n", "print(sp)\n", "print('number of blocks:', len(sp))\n" ] }, { "cell_type": "markdown", "id": "e21ffeb6", "metadata": {}, "source": [ "## 8. Words\n", "\n", "A **word** is just a sequence of letters over some alphabet. `Words` is very general and is the natural setting for things like pattern avoidance, factor complexity, Sturmian words, etc.\n" ] }, { "cell_type": "code", "execution_count": 84, "id": "a0012ea8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "8\n" ] }, { "data": { "text/plain": [ "[word: aaa,\n", " word: aab,\n", " word: aba,\n", " word: abb,\n", " word: baa,\n", " word: bab,\n", " word: bba,\n", " word: bbb]" ] }, "execution_count": 84, "metadata": {}, "output_type": "execute_result" } ], "source": [ "W = Words(['a', 'b'], 3) # all words of length 3 over {a, b}\n", "print(W.cardinality())\n", "W.list()\n" ] }, { "cell_type": "code", "execution_count": 85, "id": "fd8a053c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "length: 5\n", "number of distinct factors (substrings): 12\n", "is it a palindrome? False\n" ] } ], "source": [ "w = Word('abaab')\n", "print('length:', w.length())\n", "print('number of distinct factors (substrings):', w.number_of_factors())\n", "print('is it a palindrome?', w.is_palindrome())\n" ] }, { "cell_type": "code", "execution_count": 89, "id": "a4be2368-4cc1-408a-9898-7ed7781b3d21", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 89, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# let's count words avoiding some pattern\n", "# here we avoid consecutive 'aa'\n", "sum(1 for w in W if 'aa' not in w.string_rep())" ] }, { "cell_type": "code", "execution_count": 104, "id": "8d0611e5-5ebb-4cac-beab-751b36755cc0", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 3, 5, 8, 13, 21, 34, 55, 89]" ] }, "execution_count": 104, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# the secquence of numbers, that we all of course know\n", "[sum(1 for w in Words(['a', 'b'], n) if 'aa' not in w.string_rep()) for n in range(10)]" ] }, { "cell_type": "code", "execution_count": 105, "id": "1de11147-292c-4078-9d5a-02b4705a5e87", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]" ] }, "execution_count": 105, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[fibonacci(n) for n in range(12)]" ] }, { "cell_type": "markdown", "id": "ca65323f", "metadata": {}, "source": [ "## 9. General recipes (they work almost everywhere)\n", "\n", "Because all these families share the same interface, a handful of commands will get you very far no matter which combinatorial family you are exploring:\n", "\n", "| Task | Command |\n", "|---|---|\n", "| How many objects are there? | `Family.cardinality()` |\n", "| List them all (small cases only!) | `Family.list()` or `list(Family)` |\n", "| Iterate without building the whole list | `for x in Family: ...` |\n", "| Get one at random | `Family.random_element()` |\n", "| Get *some* fixed example | `Family.an_element()` |\n", "| Test membership | `x in Family` |\n", "| Discover available methods | `x.` (tab completion) |\n", "| Read the documentation | `Family?` or `x.method_name?` |\n", "\n", "A very handy discovery tool: the global object `combinat` groups (almost) everything together.\n" ] }, { "cell_type": "code", "execution_count": 106, "id": "5d4d0dd6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[31mInit signature:\u001b[39m DyckWords(self, x=\u001b[32m0\u001b[39m, *args, **kwds)\n", "\u001b[31mDocstring:\u001b[39m \n", " Dyck words.\n", "\n", " A Dyck word is a sequence (w_1, ..., w_n) consisting of 1 s and\n", " 0 s, with the property that for any i with 1 <= i <= n, the\n", " sequence (w_1, ..., w_i) contains at least as many 1 s as 0 s.\n", "\n", " A Dyck word is balanced if the total number of 1 s is equal to the\n", " total number of 0 s. The number of balanced Dyck words of length 2k\n", " is given by the \"Catalan number\" C_k.\n", "\n", " EXAMPLES:\n", "\n", " This class can be called with three keyword parameters \"k1\", \"k2\"\n", " and \"complete\".\n", "\n", " If neither \"k1\" nor \"k2\" are specified, then \"DyckWords\" returns\n", " the combinatorial class of all balanced (=complete) Dyck words,\n", " unless the keyword \"complete\" is set to False (in which case it\n", " returns the class of all Dyck words).\n", "\n", " sage: DW = DyckWords(); DW\n", " Complete Dyck words\n", " sage: [] in DW\n", " True\n", " sage: [1, 0, 1, 0] in DW\n", " True\n", " sage: [1, 1, 0] in DW\n", " False\n", " sage: ADW = DyckWords(complete=False); ADW\n", " Dyck words\n", " sage: [] in ADW\n", " True\n", " sage: [1, 0, 1, 0] in ADW\n", " True\n", " sage: [1, 1, 0] in ADW\n", " True\n", " sage: [1, 0, 0] in ADW\n", " False\n", "\n", " If just \"k1\" is specified, then it returns the balanced Dyck words\n", " with \"k1\" opening parentheses and \"k1\" closing parentheses.\n", "\n", " sage: DW2 = DyckWords(2); DW2\n", " Dyck words with 2 opening parentheses and 2 closing parentheses\n", " sage: DW2.first()\n", " [1, 0, 1, 0]\n", " sage: DW2.last()\n", " [1, 1, 0, 0]\n", " sage: DW2.cardinality()\n", " 2\n", " sage: DyckWords(100).cardinality() == catalan_number(100)\n", " True\n", "\n", " If \"k2\" is specified in addition to \"k1\", then it returns the Dyck\n", " words with \"k1\" opening parentheses and \"k2\" closing parentheses.\n", "\n", " sage: DW32 = DyckWords(3,2); DW32\n", " Dyck words with 3 opening parentheses and 2 closing parentheses\n", " sage: DW32.list()\n", " [[1, 0, 1, 0, 1],\n", " [1, 0, 1, 1, 0],\n", " [1, 1, 0, 0, 1],\n", " [1, 1, 0, 1, 0],\n", " [1, 1, 1, 0, 0]]\n", "\u001b[31mInit docstring:\u001b[39m\n", " Base class for all parents.\n", "\n", " Parents are the Sage/mathematical analogues of container objects in\n", " computer science.\n", "\n", " INPUT:\n", "\n", " * \"base\" -- an algebraic structure considered to be the \"base\" of\n", " this parent (e.g. the base field for a vector space)\n", "\n", " * \"category\" -- a category or list/tuple of categories. The\n", " category in which this parent lies (or list or tuple thereof).\n", " Since categories support more general super-categories, this\n", " should be the most specific category possible. If category is a\n", " list or tuple, a \"JoinCategory\" is created out of them. If\n", " category is not specified, the category will be guessed (see\n", " \"CategoryObject\"), but will not be used to inherit parent's or\n", " element's code from this category.\n", "\n", " * \"names\" -- names of generators\n", "\n", " * \"normalize\" -- whether to standardize the names (remove\n", " punctuation, etc.)\n", "\n", " * \"facade\" -- a parent, or tuple thereof, or \"True\"\n", "\n", " If \"facade\" is specified, then \"Sets().Facade()\" is added to the\n", " categories of the parent. Furthermore, if \"facade\" is not \"True\",\n", " the internal attribute \"_facade_for\" is set accordingly for use by\n", " \"Sets.Facade.ParentMethods.facade_for()\".\n", "\n", " Internal invariants:\n", "\n", " * \"self._element_init_pass_parent == guess_pass_parent(self,\n", " self._element_constructor)\" Ensures that \"__call__()\" passes down\n", " the parent properly to \"_element_constructor()\". See\n", " https://github.com/sagemath/sage/issues/5979.\n", "\n", " Todo: Eventually, category should be \"Sets\" by default.\n", "\u001b[31mFile:\u001b[39m /home/conda/feedstock_root/build_artifacts/bld/rattler-build_sagelib_1780060433/work/src/sage/structure/parent.pyx\n", "\u001b[31mType:\u001b[39m ClasscallMetaclass\n", "\u001b[31mSubclasses:\u001b[39m DyckWords_all, DyckWords_size, CompleteDyckWords" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Tab-completion tip:\n", "# Permutations(5).\n", "\n", "# Getting help on the fly:\n", "DyckWords?\n" ] }, { "cell_type": "code", "execution_count": 107, "id": "674134c7", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "number of derangements of size 6: 265\n" ] } ], "source": [ "# Iterating lazily instead of building a (potentially huge) list in memory:\n", "count = 0\n", "for p in Permutations(6):\n", " if p.number_of_fixed_points() == 0: # derangements\n", " count += 1\n", "print('number of derangements of size 6:', count)\n" ] }, { "cell_type": "code", "execution_count": 108, "id": "8c2d088f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "265" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Sanity check against Sage's dedicated Derangements class\n", "# (note: it's a separate family, not a method on Permutations)\n", "Derangements(6).cardinality()\n" ] }, { "cell_type": "markdown", "id": "89d77e6c", "metadata": { "jp-MarkdownHeadingCollapsed": true }, "source": [ "## 10. Where to go next\n", "\n", "- `sage.combinat` has *dozens* more families: `Tableaux`, `BinaryTrees`, `OrderedTrees`, `Graphs`, `Posets`, `Matroids`, `RootSystem`, `SymmetricFunctions`, ...\n", "- The official thematic tutorial is a great next step: **\"Sage combinatorics tutorial\"**.\n", "- Whenever you wonder \"does Sage have X?\", just try `X = ...` with a capital letter and press **Tab**, or search the reference manual for `sage.combinat`.\n", "\n", "### Quick reference cheat-sheet\n", "\n", "```\n", "Permutations(n) # permutations of {1,...,n}\n", "DyckWords(n) # Dyck words of semilength n (Catalan numbers)\n", "BinaryTrees(n) # binary trees with n nodes (same Catalan numbers)\n", "Compositions(n) # ordered sums to n\n", "Partitions(n) # unordered sums to n\n", "SetPartitions(n) # partitions of a set into blocks (Bell numbers)\n", "Words(alphabet, length) # words over a fixed alphabet\n", "\n", "ascii_art(obj) # generic, presentation-friendly text drawing --\n", " # works on Dyck words, trees, partitions, tableaux, ...\n", "```\n" ] }, { "cell_type": "markdown", "id": "c26b231f-2a19-45c5-95d2-a6616dcfe56f", "metadata": {}, "source": [ "## 11. Glimpse at generating functions and lattice paths\n", "\n", "You already use generating functions daily in Maple. The good news: the *idea* in Sage is exactly the same — a sequence $(a_n)_{n\\ge 0}$ is packaged into a formal power series\n", "$$ A(x) = \\sum_{n \\ge 0} a_n x^n, $$\n", "and a combinatorial decomposition of the objects translates into a functional/algebraic equation satisfied by $A(x)$. What changes is only the *syntax*. Let's see this on our favourite example — Dyck paths — end to end: from counting objects, to a functional equation, to a closed form, to asymptotics.\n" ] }, { "cell_type": "markdown", "id": "d3cf7564-59e5-420f-897e-7180debac8c7", "metadata": {}, "source": [ "### Step 1 — just look at the counting sequence\n", "\n", "We already know how to get the counting sequence *combinatorially*, one cardinality at a time.\n" ] }, { "cell_type": "code", "execution_count": 162, "id": "28b2a3b5-05b5-430c-91ec-4f48f08a623f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]" ] }, "execution_count": 162, "metadata": {}, "output_type": "execute_result" } ], "source": [ "catalan_seq = [DyckWords(n).cardinality() for n in range(11)]\n", "catalan_seq\n" ] }, { "cell_type": "markdown", "id": "f4982cc8-b699-4e1c-bc30-dfcfbf6ba498", "metadata": {}, "source": [ "### A little bonus: let Sage identify the sequence for you\n", "\n", "Sage can query the **OEIS** (Online Encyclopedia of Integer Sequences) directly from a Jupyter cell. This is a genuinely useful research habit, not just a party trick: whenever a mysterious integer sequence falls out of a computation, this is often the fastest way to discover it already has a name, a generating function, and 200 references.\n" ] }, { "cell_type": "code", "execution_count": 163, "id": "cc4a5c1e-69c5-483e-acc0-ce0330c04cb3", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "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: A287974: Number of Dyck paths of semilength n such that no level has more than ten peaks." ] }, "execution_count": 163, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# needs internet access; comment out if you are offline during the talk\n", "oeis(catalan_seq)\n" ] }, { "cell_type": "markdown", "id": "66f43dff-c28f-46bb-811b-6cb70cb1f50f", "metadata": {}, "source": [ "### Step 2 — where the functional equation comes from\n", "\n", "Every non-empty Dyck path decomposes **uniquely** at its first return to height $0$:\n", "\n", "$$ \\text{(nonempty Dyck path)} \\;=\\; \\mathsf{U} \\cdot (\\text{Dyck path}) \\cdot \\mathsf{D} \\cdot (\\text{Dyck path}). $$\n", "\n", "Translating \"$\\cdot$\" into product of generating functions and \"one up/down step\" into a factor of $x$ (one for the up-step and one for the down-step, since together they contribute semilength $1$) gives the classical algebraic equation\n", "$$ C(x) = 1 + x\\, C(x)^2, $$\n", "where the $1$ accounts for the empty path. This single line *is* the combinatorial content — everything from here on is just solving it.\n" ] }, { "cell_type": "code", "execution_count": 164, "id": "c9320321-6f3d-4773-a558-e0ba1614085f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[C(x) == -1/2*(sqrt(-4*x + 1) - 1)/x, C(x) == 1/2*(sqrt(-4*x + 1) + 1)/x]" ] }, "execution_count": 164, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Solving the functional equation symbolically, exactly like you would on paper\n", "var('x')\n", "C = function('C')(x)\n", "eq = C == 1 + x * C^2\n", "solutions = solve(eq, C)\n", "solutions\n" ] }, { "cell_type": "markdown", "id": "e7102dd5-398e-4906-b120-71ea1b812457", "metadata": {}, "source": [ "There are two roots of the quadratic; only one of them is the *correct* generating function, namely the one satisfying $C(0) = 1$ (the empty Dyck path is the only one of semilength $0$). Looking at the two closed forms above, the branch with the **minus** sign in front of the square root is the right one (the **plus** branch blows up as $x \\to 0$).\n" ] }, { "cell_type": "code", "execution_count": 165, "id": "03518867-d2b1-40e3-aa29-87d6d1586025", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-1/2*(sqrt(-4*x + 1) - 1)/x" ] }, "execution_count": 165, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Cx = solutions[0].rhs() # pick the minus-sign branch -- adjust the index if Sage orders them differently\n", "Cx\n" ] }, { "cell_type": "code", "execution_count": 166, "id": "27dd5113-168b-416d-b0fa-d0b7d83dd5cf", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 166, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# sanity check: does it really satisfy C(0) = 1 ?\n", "Cx.limit(x=0)\n", "\n", "# Cx.subs(x=0) # creates an error\n" ] }, { "cell_type": "markdown", "id": "a0849035-381b-4fa0-b247-c663a1c24edf", "metadata": {}, "source": [ "### Step 3 — turning the closed form back into a power series\n", "\n", "This is the Sage counterpart of Maple's `series`/`taylor`: expand the symbolic expression as a Taylor series around $x=0$, then read off the coefficients.\n" ] }, { "cell_type": "code", "execution_count": 167, "id": "9a0cc5a6-7b46-463e-9cfc-84f23f6e8fc0", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "16796*x^10 + 4862*x^9 + 1430*x^8 + 429*x^7 + 132*x^6 + 42*x^5 + 14*x^4 + 5*x^3 + 2*x^2 + x + 1" ] }, "execution_count": 167, "metadata": {}, "output_type": "execute_result" } ], "source": [ "series_expansion = Cx.taylor(x, 0, 10)\n", "series_expansion\n" ] }, { "cell_type": "code", "execution_count": 168, "id": "95dc9d28-28b4-46a7-8c8e-be70cdfa68e8", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]" ] }, "execution_count": 168, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Extract just the coefficients [a_0, a_1, ..., a_10] to compare with our combinatorial count\n", "coeffs_from_gf = [series_expansion.coefficient(x, n) for n in range(11)]\n", "coeffs_from_gf\n" ] }, { "cell_type": "code", "execution_count": 169, "id": "03f7ac96-55ad-49af-a207-c5b6b1208813", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 169, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The punchline: counting the objects directly and solving the functional equation\n", "# give EXACTLY the same numbers.\n", "coeffs_from_gf == catalan_seq\n" ] }, { "cell_type": "code", "execution_count": 106, "id": "6f3e81f6-06f4-45e1-ae24-e1cb12de747a", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "exact C_30 = 3814986502092304\n", "asymptotic estimate = 3958611859443421.5\n", "ratio (should -> 1): 0.9637182521422266\n" ] } ], "source": [ "# Let's just check the asymptotic formula numerically against the exact value\n", "n = 30\n", "exact = catalan_number(n)\n", "asymptotic = 4^n / (sqrt(pi) * n^(3/2))\n", "print('exact C_%d =' % n, exact)\n", "print('asymptotic estimate =', float(asymptotic))\n", "print('ratio (should -> 1):', float(exact / asymptotic))\n" ] }, { "cell_type": "markdown", "id": "e9fe715e-26a0-421b-a2ca-7a3a4d65d94f", "metadata": {}, "source": [ "**Take-away for the audience:** Sage's `sage.combinat` classes are perfect for the *finite, exact, combinatorial* side of the story (enumerate, count, sample, decompose). The moment you package a counting sequence into a generating function — using nothing more exotic than `solve`, `.taylor()`, and `.coefficient()` — you are standing exactly on the bridge into asymptotics and analytic combinatorics.\n" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 10.9", "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.12.13" } }, "nbformat": 4, "nbformat_minor": 5 }