tutorial-integer-partitions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "$$\n",
    "\\def\\CC{\\bf C}\n",
    "\\def\\QQ{\\bf Q}\n",
    "\\def\\RR{\\bf R}\n",
    "\\def\\ZZ{\\bf Z}\n",
    "\\def\\NN{\\bf N}\n",
    "$$\n",
    "# Partitions and Young tableaux tutorial\n",
    "\n",
    "Mélodie Lapointe (<lapointe.melodie@courrier.uqam.ca>) and Pauline Hubert (<hubert.pauline@courrier.uqam.ca>)\n",
    "\n",
    "\n",
    "## Partitions\n",
    "\n",
    "Recall that a <span style=\"color:blue\">__partition__</span> $\\mu$ of $n$, one writes $\\mu\\vdash n$ or $n=|\\mu|$, is a sequence of integers $(\\mu_0,\\mu_1,\\ldots, \\mu_{k-1})$ (the $m_i$'s are the <span style=\"color:blue\">__parts__</span> of $\\mu$) with $\\mu_0\\geq \\mu_1\\geq\\,\\cdots\\,\\geq\\mu_{k-1}>0$, and $n=\\mu_0+\\mu_1+\\ldots+\\mu_{k-1}$. The number $\\ell(\\mu):=k$ of parts of $\\mu$ is said to be its  <span style=\"color:blue\">__length__</span>. A partition $\\mu$ may also be described as a <span style=\"color:blue\">__Ferrers diagram__</span>, which is the $n$-subset of $\\mathbb{N}\\times \\mathbb{N}$:\n",
    "\n",
    "#### $$\\{(a,b)\\ |\\ 0\\leq a<\\mu_i\\quad{\\rm and}\\quad b<\\ell(\\mu)\\}.$$\n",
    "This set is also denoted $\\mu$, and its elements are the  <span style=\"color:blue\">__cells__</span> of $\\mu$. \n",
    "The <span style=\"color:blue\">__conjuguate__</span> of $\\mu$, is the partition $\\mu'$ such that\n",
    "\n",
    "#### $$ \\mu'=\\{(b,a)\\ |\\ (a,b)\\in\\mu\\}.$$\n",
    "Parts of $\\mu$ are the lengths of the <span style=\"color:blue\">__rows__</span> of its diagram, and parts of $\\mu'$ are the lengths of its <span style=\"color:blue\">__columns__</span>.\n",
    "\n",
    "For more, see https://en.wikipedia.org/wiki/Partition_(number_theory)\n",
    "\n",
    "We mostly follow the notation conventions of Macdonald's book: *Symmetric Functions and Hall Polynomials*, Second Edition,\n",
    "Oxford Mathematical Monographs, 1998.\n",
    "\n",
    "Here are <span style=\"color:blue\">__a few preliminary declarations__</span> just to make outputs nicer, and diagrams to printout with the <span style=\"color:blue\">__French convention__</span>. Partitions parts are glued together, with parts of size larger that $9$ ending with a \"dot\" so that there is no confusion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "%display latex\n",
    "def mystr(i): \n",
    "    if i<10: \n",
    "        return str(i) \n",
    "    else: \n",
    "        return ''.join([str(i),\".\"])\n",
    "def compact(mu): \n",
    "    return (''.join(mystr(i) for i in mu))\n",
    "\n",
    "Partition._latex_= compact"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Handling partitions in SAGE\n",
    "\n",
    "Partition can be created/declared in SAGE the following way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}10.10.221</script></html>"
      ],
      "text/plain": [
       "[10, 10, 2, 2, 1]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mu=Partition([10,10,2,2,1]); mu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Nice format versus normal one\n",
    "\n",
    "with $\\mu$ here printed out in a nicer format than the usual:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 10, 2, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "print(Partition([10,10,2,2,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Listing partitions of $n$\n",
    "\n",
    "One can also list all partitions of a given integer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[4, 31, 22, 211, 1111\\right]</script></html>"
      ],
      "text/plain": [
       "[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Partitions(4).list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "###  Number of partitions\n",
    "\n",
    "Or simply calculate the number of partitions of $n$. \n",
    "\n",
    "(We underline that this function does not actually generate the partitions of $n$ in order to count them; hence it is amazingly fast.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}496025142797537184410324879054927095334462742231683423624</script></html>"
      ],
      "text/plain": [
       "496025142797537184410324879054927095334462742231683423624"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Partitions(3000).cardinality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519\n"
     ]
    }
   ],
   "source": [
    "print(Partitions(100000).cardinality())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Partitions with constraints\n",
    "\n",
    "One may add constraints on partitions; for instance, to get partitions of 5 of length 2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[41, 32\\right]</script></html>"
      ],
      "text/plain": [
       "[[4, 1], [3, 2]]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = Partitions(5,length=2)\n",
    "p.list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "or get all partitions of 6 with length between 3 and 5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[411, 321, 3111, 222, 2211, 21111\\right]</script></html>"
      ],
      "text/plain": [
       "[[4, 1, 1], [3, 2, 1], [3, 1, 1, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1]]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = Partitions(6,min_length=3,max_length=5)\n",
    "p.list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Ferrers diagram \n",
    "\n",
    "By default SAGE uses the English convention, but it has become the tradition in recent years to use the more natural (cartesian coordinates) French notation. Here is how to set this"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "Partitions.options.convention=\"french\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "********\n",
      "*****\n",
      "*****\n",
      "*****\n",
      "****\n",
      "***\n",
      "***\n",
      "**\n"
     ]
    }
   ],
   "source": [
    "mu = Partition([8,5,5,5,4,3,3,2])\n",
    "print(mu.ferrers_diagram())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Cells\n",
    "\n",
    "The list of cells of $m$ my be obtained as follows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[\\left(0, 0\\right), \\left(0, 1\\right), \\left(0, 2\\right), \\left(0, 3\\right), \\left(0, 4\\right), \\left(0, 5\\right), \\left(0, 6\\right), \\left(0, 7\\right), \\left(1, 0\\right), \\left(1, 1\\right), \\left(1, 2\\right), \\left(1, 3\\right), \\left(1, 4\\right), \\left(2, 0\\right), \\left(2, 1\\right), \\left(2, 2\\right), \\left(2, 3\\right), \\left(2, 4\\right), \\left(3, 0\\right), \\left(3, 1\\right), \\left(3, 2\\right), \\left(3, 3\\right), \\left(3, 4\\right), \\left(4, 0\\right), \\left(4, 1\\right), \\left(4, 2\\right), \\left(4, 3\\right), \\left(5, 0\\right), \\left(5, 1\\right), \\left(5, 2\\right), \\left(6, 0\\right), \\left(6, 1\\right), \\left(6, 2\\right), \\left(7, 0\\right), \\left(7, 1\\right)\\right]</script></html>"
      ],
      "text/plain": [
       "[(0, 0),\n",
       " (0, 1),\n",
       " (0, 2),\n",
       " (0, 3),\n",
       " (0, 4),\n",
       " (0, 5),\n",
       " (0, 6),\n",
       " (0, 7),\n",
       " (1, 0),\n",
       " (1, 1),\n",
       " (1, 2),\n",
       " (1, 3),\n",
       " (1, 4),\n",
       " (2, 0),\n",
       " (2, 1),\n",
       " (2, 2),\n",
       " (2, 3),\n",
       " (2, 4),\n",
       " (3, 0),\n",
       " (3, 1),\n",
       " (3, 2),\n",
       " (3, 3),\n",
       " (3, 4),\n",
       " (4, 0),\n",
       " (4, 1),\n",
       " (4, 2),\n",
       " (4, 3),\n",
       " (5, 0),\n",
       " (5, 1),\n",
       " (5, 2),\n",
       " (6, 0),\n",
       " (6, 1),\n",
       " (6, 2),\n",
       " (7, 0),\n",
       " (7, 1)]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mu.cells()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "and printed out in nice format as"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[00, 01, 02, 03, 04, 05, 06, 07, 10, 11, 12, 13, 14, 20, 21, 22, 23, 24, 30, 31, 32, 33, 34, 40, 41, 42, 43, 50, 51, 52, 60, 61, 62, 70, 71\\right]</script></html>"
      ],
      "text/plain": [
       "['00',\n",
       " '01',\n",
       " '02',\n",
       " '03',\n",
       " '04',\n",
       " '05',\n",
       " '06',\n",
       " '07',\n",
       " '10',\n",
       " '11',\n",
       " '12',\n",
       " '13',\n",
       " '14',\n",
       " '20',\n",
       " '21',\n",
       " '22',\n",
       " '23',\n",
       " '24',\n",
       " '30',\n",
       " '31',\n",
       " '32',\n",
       " '33',\n",
       " '34',\n",
       " '40',\n",
       " '41',\n",
       " '42',\n",
       " '43',\n",
       " '50',\n",
       " '51',\n",
       " '52',\n",
       " '60',\n",
       " '61',\n",
       " '62',\n",
       " '70',\n",
       " '71']"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "map(compact,mu.cells())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "If one insists on using the English convention, rather than akwardly reading this notebook \"<span style=\"color:blue\">__... upside down, in a mirror ...__</span>\" (as Macdonald would say), one could globally switch back as follows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "********\n",
      "*****\n",
      "*****\n",
      "*****\n",
      "****\n",
      "***\n",
      "***\n",
      "**\n"
     ]
    }
   ],
   "source": [
    "Partitions.options(convention='english')\n",
    "print(mu.ferrers_diagram())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Partition containment\n",
    "\n",
    "A partition $\\mu$ is said to be <span style=\"color:blue\">__included__</span> in a partition $\\lambda$ if $\\mu_i \\leq \\lambda_i$, for all $i$. In other words, the diagram of $\\mu$ is a subset of the diagram of $\\lambda$. For example, one can list all partitions $\\lambda$ of $5$ such that the partition $[2,1]$ is included in $\\lambda$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[41, 32, 311, 221, 2111\\right]</script></html>"
      ],
      "text/plain": [
       "[41, 32, 311, 221, 2111]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = Partitions(5,inner= [2,1])\n",
    "p.list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Or all partitions of 5 included in the partition $[4,3,2,1]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[41, 32, 311, 221, 2111\\right]</script></html>"
      ],
      "text/plain": [
       "[41, 32, 311, 221, 2111]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = Partitions(5,outer=[4,3,2,1])\n",
    "p.list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The default (total) order on partitions is the lexicographic order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}</script></html>"
      ],
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mu = Partition([4,3,3])\n",
    "nu = Partition([4,4,1])\n",
    "mu < nu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Exercise:\n",
    "\n",
    "> *Let $\\lambda$ be the partition $[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]$. Compute *\n",
    "\n",
    "$$\\sum\\limits_{i=0}^{20} \\sum\\limits_{\\mu \\vdash i,\\ \\mu \\subseteq \\lambda} q^i.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}476 \\, q^{19} + 377 \\, q^{18} + 293 \\, q^{17} + 229 \\, q^{16} + 176 \\, q^{15} + 135 \\, q^{14} + 101 \\, q^{13} + 77 \\, q^{12} + 56 \\, q^{11} + 42 \\, q^{10} + 30 \\, q^{9} + 22 \\, q^{8} + 15 \\, q^{7} + 11 \\, q^{6} + 7 \\, q^{5} + 5 \\, q^{4} + 3 \\, q^{3} + 2 \\, q^{2} + q + 1</script></html>"
      ],
      "text/plain": [
       "476*q^19 + 377*q^18 + 293*q^17 + 229*q^16 + 176*q^15 + 135*q^14 + 101*q^13 + 77*q^12 + 56*q^11 + 42*q^10 + 30*q^9 + 22*q^8 + 15*q^7 + 11*q^6 + 7*q^5 + 5*q^4 + 3*q^3 + 2*q^2 + q + 1"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q=var('q')\n",
    "\n",
    "mu=[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]\n",
    "\n",
    "sum(Partitions(i,outer=mu).cardinality()*q^i for i in range(20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Young Tableaux\n",
    "\n",
    "An $A$-valued <span style=\"color:blue\">__Young tableaux__</span> of <span style=\"color:blue\">__shape__</span> $\\mu$ is a \"filling\" the cells of the Ferrers diagram of $\\mu$ with elements of an ordered set $A$. Hence it is a function $\\tau:\\mu\\rightarrow A$. A tableau is said to <span style=\"color:blue\">__standard__</span> if it is bijective (hence $A$ has cardinality equal to the number of cells of $\\mu$), and its entries on each row (and each column) are stricly increasing from left to right (from bottom to top in french convention). A tableau (not necessarily bijective) is said to be <span style=\"color:blue\">__semistandard__</span> if its entries are weakly increasing from left to right on each row, and strictly increasing on each column. \n",
    "These object may be constructed in the following way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  8\n",
      "  5  7\n",
      "  3  3  6\n",
      "  1  2  4\n",
      "\n",
      "  8\n",
      "  5  7\n",
      "  3  6\n",
      "  1  2  4\n"
     ]
    }
   ],
   "source": [
    "t = SemistandardTableau([[1,2,4],[3,3,6],[5,7],[8]])\n",
    "t.pp()\n",
    "print('')\n",
    "s = StandardTableau([[1,2,4],[3,6],[5,7],[8]]) \n",
    "s.pp()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The function pp($\\ $) (\"pp\" stands for pretty print) gives a nicer display for Young tableaux. Observe that if you set options (like French vs English convention) for partitions, these will also apply to Young tableaux.\n",
    "\n",
    "It is also possible to list all semistandard and standard Young tableaux of a given partition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "390780390\n",
      "15015\n"
     ]
    }
   ],
   "source": [
    "x = SemistandardTableaux([4,3,3,2,1])\n",
    "print(x.cardinality())\n",
    "y = StandardTableaux([4,3,3,2,1])\n",
    "print(y.cardinality())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "The functions for partitions, such as display, options, cardinality, and list, may also be used on Young tableaux.\n",
    "\n",
    "### Exercise:\n",
    "\n",
    "> *Verify that the number of standard Young tableaux of shape $[n,n]$ is equal to the Catalan number for $0 \\leq n \\leq 20$. (The function catalan\\_number($n$) returns the nth catalan number).*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}</script></html>"
      ],
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all(catalan_number(i)==StandardTableaux([i,i]).cardinality() for i in range(1,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Exercise:\n",
    "\n",
    "> *Compute the sum of all monomials of degree 5 in three variables using partitions and standard tableaux.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}x^{5} + 2 \\, x^{4} y + 3 \\, x^{3} y^{2} + 3 \\, x^{2} y^{3} + 2 \\, x y^{4} + y^{5} + 2 \\, x^{4} z + 5 \\, x^{3} y z + 7 \\, x^{2} y^{2} z + 5 \\, x y^{3} z + 2 \\, y^{4} z + 3 \\, x^{3} z^{2} + 7 \\, x^{2} y z^{2} + 7 \\, x y^{2} z^{2} + 3 \\, y^{3} z^{2} + 3 \\, x^{2} z^{3} + 5 \\, x y z^{3} + 3 \\, y^{2} z^{3} + 2 \\, x z^{4} + 2 \\, y z^{4} + z^{5}</script></html>"
      ],
      "text/plain": [
       "x^5 + 2*x^4*y + 3*x^3*y^2 + 3*x^2*y^3 + 2*x*y^4 + y^5 + 2*x^4*z + 5*x^3*y*z + 7*x^2*y^2*z + 5*x*y^3*z + 2*y^4*z + 3*x^3*z^2 + 7*x^2*y*z^2 + 7*x*y^2*z^2 + 3*y^3*z^2 + 3*x^2*z^3 + 5*x*y*z^3 + 3*y^2*z^3 + 2*x*z^4 + 2*y*z^4 + z^5"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "var('x y z')\n",
    "young_tableaux = []\n",
    "monomials = []\n",
    "for i in Partitions(5).list():\n",
    "    young_tableaux.extend(SemistandardTableaux(i,max_entry=3).list())\n",
    "for j in young_tableaux:\n",
    "    k = reduce(operator.add,j)\n",
    "    monomials.append(x^k.count(1)*y^k.count(2)*z^k.count(3))\n",
    "show(sum(monomials))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Hook formula for the number of standard tableaux of shape $\\mu$\n",
    "\n",
    "The classical hook formula \n",
    "   \n",
    " $$ f^\\mu:=\\frac{n!}{\\prod_{c\\in\\mu} h(c,\\mu)},$$\n",
    " with $h((i,j),\\mu):= \\mu_i+\\mu'_j-i-j-1$,\n",
    "may be encoded as"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def hook_formula(mu): \n",
    "    mu=Partition(mu)\n",
    "    return factorial(add(k for k in mu))/prod(mu.hook_length(i,j) for i,j in mu.cells())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}216</script></html>"
      ],
      "text/plain": [
       "216"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hook_formula(Partition([4,3,1,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "### Here are some functions on partitions often used in the theory of Macdonald polynomials\n",
    "\n",
    "(Sometimes one may want a more functional notation for combinatorial calculations on diagrams.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "\n",
    "\\begin{eqnarray}\n",
    "  && n(\\mu):=\\sum_{(i,j)\\in\\mu} i,\n",
    "\\qquad T_\\mu:=\\prod_{(i,j)\\in\\mu} t^iq^j,\\\\\n",
    "&& B_\\mu:=\\sum_{(i,j)\\in\\mu} t^iq^j,\n",
    "\\qquad \\Pi_\\mu:=\\prod_{(i,j)\\in\\mu,\\ (i,j)\\not=(0,0)} (1-t^iq^j),\\\\\n",
    "  &&\\varepsilon_\\mu:=\\prod_{c\\in\\mu}(q^{a(c)}-t^{l(c)+1})(t^{l(c)}-q^{a(c)+1}),\n",
    " \\end{eqnarray}\n",
    "where $a(c)$ et $l(c)$ respectively denote the arm and the leg of a cell  $c$ in $\\mu$.\n",
    "We have\n",
    "\n",
    "$$ (n(\\mu),n(\\mu'))=\\sum_{c \\in \\mu} c.$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "q,t=var('q,t')\n",
    "\n",
    "def ell(mu):\n",
    "    mu=Partition(mu)\n",
    "    return mu.length()\n",
    "\n",
    "def arm(c,mu): \n",
    "    mu=Partition(mu)\n",
    "    return mu.arm_length(c[0],c[1])\n",
    "\n",
    "def leg(c,mu): \n",
    "    mu=Partition(mu)\n",
    "    return mu.leg_length(c[0],c[1])\n",
    "\n",
    "def corner_cells(mu): \n",
    "    mu=Partition(mu)\n",
    "    return mu.corners()\n",
    "\n",
    "def zee(mu): \n",
    "    mu=Partition(mu)\n",
    "    return mu.aut()\n",
    "\n",
    "def n(mu): return add(i for i,j in mu.cells())\n",
    "\n",
    "def B(mu):\n",
    "    return add(t^i*q^j for i,j in mu.cells())\n",
    "\n",
    "def T(mu):\n",
    "    return prod(t^i*q^j for i,j in mu.cells())\n",
    "\n",
    "def Pi(mu):\n",
    "    return prod(1-t^i*q^j for i,j in mu.cells() if [i,j]<>[0,0])\n",
    "\n",
    "def epsilon(mu): \n",
    "    return prod((q^(arm(c,mu))-t^(1+leg(c,mu)))*(t^(leg(c,mu))-q^(1+arm(c,mu))) for c in mu.cells())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "mu=Partition([4,3,3,1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}</script></html>"
      ],
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vector([n(mu),n(mu.conjugate())])== add(vector(c) for c in mu.cells())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}q^{2} t^{2} + t^{4} + q^{3} + q^{2} t + q t^{2} + t^{3} + q^{2} + q t + t^{2} + q + t + 1</script></html>"
      ],
      "text/plain": [
       "q^2*t^2 + t^4 + q^3 + q^2*t + q*t^2 + t^3 + q^2 + q*t + t^2 + q + t + 1"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "B(mu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}-{\\left(q^{2} t^{2} - 1\\right)} {\\left(t^{4} - 1\\right)} {\\left(q^{3} - 1\\right)} {\\left(q^{2} t - 1\\right)} {\\left(q t^{2} - 1\\right)} {\\left(t^{3} - 1\\right)} {\\left(q^{2} - 1\\right)} {\\left(q t - 1\\right)} {\\left(t^{2} - 1\\right)} {\\left(q - 1\\right)} {\\left(t - 1\\right)}</script></html>"
      ],
      "text/plain": [
       "-(q^2*t^2 - 1)*(t^4 - 1)*(q^3 - 1)*(q^2*t - 1)*(q*t^2 - 1)*(t^3 - 1)*(q^2 - 1)*(q*t - 1)*(t^2 - 1)*(q - 1)*(t - 1)"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Pi(mu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\frac{1}{720} \\, {\\left(k + 5\\right)} {\\left(k + 4\\right)} {\\left(k + 3\\right)} {\\left(k + 2\\right)} {\\left(k + 1\\right)} k</script></html>"
      ],
      "text/plain": [
       "1/720*(k + 5)*(k + 4)*(k + 3)*(k + 2)*(k + 1)*k"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k=var('k')\n",
    "\n",
    "factor(add(k^ell(mu)/zee(mu) for mu in Partitions(6)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\frac{1}{720} \\, {\\left(k - 1\\right)} {\\left(k - 2\\right)} {\\left(k - 3\\right)} {\\left(k - 4\\right)} {\\left(k - 5\\right)} k</script></html>"
      ],
      "text/plain": [
       "1/720*(k - 1)*(k - 2)*(k - 3)*(k - 4)*(k - 5)*k"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(add((-k)^ell(mu)/zee(mu) for mu in Partitions(6)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.0.beta0",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}