{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Example 2.2 (Compositions and Partitions)\n", "A short investigation of compositions and partitions in Sage. More details can be found in the documentation for [compositions](https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/composition.html) and [partitions](https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/partition.html). \n", "*Requirements: None*" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The class [Compositions of 10] has 512 elements\n", "A random element of [Compositions of 10] is [1, 1, 1, 1, 5, 1]\n" ] } ], "source": [ "# The compositions of a fixed integer n can be easily manipulated using Sage\n", "C = Compositions(10)\n", "print(\"The class [{}] has {} elements\".format(C,C.cardinality()))\n", "print(\"A random element of [{}] is {}\".format(C,C.random_element()))" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The class [Partitions of the integer 20] has 627 elements\n", "A random element of [Partitions of the integer 20] is [8, 3, 2, 2, 2, 1, 1, 1]\n" ] } ], "source": [ "# The paritions of a fixed integer behave similarly\n", "P = Partitions(20)\n", "print(\"The class [{}] has {} elements\".format(P,P.cardinality()))\n", "print(\"A random element of [{}] is {}\".format(P,P.random_element()))" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The partition [5, 3, 3, 3, 2, 1, 1, 1, 1] has Ferrers diagram \n" ] }, { "data": { "text/html": [ "" ], "text/latex": [ "\\begin{math}\n", "\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\begin{array}{l}\n", "\\verb|*****|\\\\\n", "\\verb|***|\\\\\n", "\\verb|***|\\\\\n", "\\verb|***|\\\\\n", "\\verb|**|\\\\\n", "\\verb|*|\\\\\n", "\\verb|*|\\\\\n", "\\verb|*|\\\\\n", "\\verb|*|\n", "\\end{array}\n", "\\end{math}" ], "text/plain": [ "'*****\\n***\\n***\\n***\\n**\\n*\\n*\\n*\\n*'" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Partitions can be displayed graphically by their Ferrers diagram\n", "p = P.random_element()\n", "print(\"The partition {} has Ferrers diagram \".format(p))\n", "show(p.ferrers_diagram())" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The class [Partitions of the integer 20 satisfying constraints max_length=5, max_part=10] has 121 elements\n", "A random element in this class is [7, 7, 2, 2, 2]\n" ] } ], "source": [ "# We can impose various constraints on the partitions\n", "# Here we count partitions of 20 with at most 5 summands, each of size at most 10\n", "Pbox = Partitions(20, max_part=10, max_length=5)\n", "print(\"The class [{}] has {} elements\".format(Pbox,Pbox.cardinality()))\n", "print(\"A random element in this class is {}\".format(Pbox.random_element()))" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1, 2, 4, 8, 16, 32, 64, 128, 256]\n", "[1, 1, 2, 4, 8, 16, 32, 64, 128, 256]\n" ] } ], "source": [ "# The generating function of compositions is a geometric series\n", "# Whether or not there is a composition of size zero is a matter of convention\n", "var('z')\n", "C = z/(1-2*z)\n", "print(C.series(z,10).list()) # Series coefficients of geometric series\n", "print([Compositions(k).cardinality() for k in range(10)]) # Actual count of compositions" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 1, 2, 3, 5, 7, 11, 15, 22, 30]\n", "[1, 1, 2, 3, 5, 7, 11, 15, 22, 30]\n" ] } ], "source": [ "# The generating function of partitions is an infinite product, but only a finite number of terms determine a fixed number of initial terms\n", "var('z')\n", "def partition_series(N):\n", " return mul([1/(1-z^k) for k in range(1,N+1)]).series(z,N)\n", "\n", "print(partition_series(10).list())\n", "print([Partitions(k).cardinality() for k in range(10)]) # Actual count of partitions" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.2", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }