.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/combinatorics/special_numbers/plot_02_catalan_numbers.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_combinatorics_special_numbers_plot_02_catalan_numbers.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_combinatorics_special_numbers_plot_02_catalan_numbers.py:


Catalan numbers: Euler's polygon triangulations and Catalan's brackets
===========================================================================

Draws all 14 triangulations of a convex hexagon, the problem Euler
posed to Goldbach in 1751, and checks that the same Catalan numbers
count balanced parenthesizations, Catalan's bracketing problem of 1838.

.. GENERATED FROM PYTHON SOURCE LINES 11-45

.. code-block:: Python

    import itertools

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.combinatorics import catalan_number, combinations_count


    def _triangulations(vertices):
        """All triangulations of the convex polygon ``vertices``, as lists of diagonals."""
        if len(vertices) < 3:
            return [[]]
        a, b = vertices[0], vertices[-1]
        result = []
        # The edge a-b lies in exactly one triangle (a, c, b); recurse on both sides.
        for i in range(1, len(vertices) - 1):
            c = vertices[i]
            chords = [(a, c)] if i > 1 else []
            chords += [(c, b)] if i < len(vertices) - 2 else []
            for left in _triangulations(vertices[: i + 1]):
                for right in _triangulations(vertices[i:]):
                    result.append(chords + left + right)
        return result


    def _is_balanced(s):
        depth = 0
        for ch in s:
            depth += 1 if ch == "(" else -1
            if depth < 0:
                return False
        return depth == 0









.. GENERATED FROM PYTHON SOURCE LINES 46-48

Euler's problem: triangulations of a convex (n+2)-gon
---------------------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 48-54

.. code-block:: Python


    for n in range(1, 8):
        count = len(_triangulations(list(range(n + 2))))
        print(f"{n + 2}-gon: {count:4d} triangulations, C_{n} = {catalan_number(n)}")
        assert count == catalan_number(n)





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    3-gon:    1 triangulations, C_1 = 1
    4-gon:    2 triangulations, C_2 = 2
    5-gon:    5 triangulations, C_3 = 5
    6-gon:   14 triangulations, C_4 = 14
    7-gon:   42 triangulations, C_5 = 42
    8-gon:  132 triangulations, C_6 = 132
    9-gon:  429 triangulations, C_7 = 429




.. GENERATED FROM PYTHON SOURCE LINES 55-57

Catalan's problem: balanced parenthesizations
---------------------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 57-64

.. code-block:: Python


    for n in range(1, 7):
        balanced = sum(_is_balanced(s) for s in itertools.product("()", repeat=2 * n))
        closed_form = combinations_count(2 * n, n) // (n + 1)
        print(f"n={n}: {balanced:3d} balanced strings, C_{n} = {catalan_number(n)}, binom(2n,n)/(n+1) = {closed_form}")
    print("n=3:", ["".join(s) for s in itertools.product("()", repeat=6) if _is_balanced(s)])





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    n=1:   1 balanced strings, C_1 = 1, binom(2n,n)/(n+1) = 1
    n=2:   2 balanced strings, C_2 = 2, binom(2n,n)/(n+1) = 2
    n=3:   5 balanced strings, C_3 = 5, binom(2n,n)/(n+1) = 5
    n=4:  14 balanced strings, C_4 = 14, binom(2n,n)/(n+1) = 14
    n=5:  42 balanced strings, C_5 = 42, binom(2n,n)/(n+1) = 42
    n=6: 132 balanced strings, C_6 = 132, binom(2n,n)/(n+1) = 132
    n=3: ['((()))', '(()())', '(())()', '()(())', '()()()']




.. GENERATED FROM PYTHON SOURCE LINES 65-67

The 14 triangulations of a hexagon
---------------------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 67-80

.. code-block:: Python


    angles = np.pi / 2 + 2 * np.pi * np.arange(6) / 6
    pts = np.column_stack([np.cos(angles), np.sin(angles)])
    fig, axes = plt.subplots(2, 7, figsize=(12, 3.8))
    for ax, diagonals in zip(axes.flat, _triangulations(list(range(6)))):
        ax.fill(pts[:, 0], pts[:, 1], color="C0", alpha=0.12)
        ax.plot(*np.vstack([pts, pts[:1]]).T, color="C0", lw=1.5)
        for i, j in diagonals:
            ax.plot(*pts[[i, j]].T, color="C3", lw=1.5)
        ax.set_aspect("equal")
        ax.axis("off")
    fig.suptitle(f"Euler's problem: a hexagon has $C_4 = {catalan_number(4)}$ triangulations")
    fig.tight_layout()



.. image-sg:: /api/gallery/combinatorics/special_numbers/images/sphx_glr_plot_02_catalan_numbers_001.png
   :alt: Euler's problem: a hexagon has $C_4 = 14$ triangulations
   :srcset: /api/gallery/combinatorics/special_numbers/images/sphx_glr_plot_02_catalan_numbers_001.png
   :class: sphx-glr-single-img






.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.049 seconds)


.. _sphx_glr_download_api_gallery_combinatorics_special_numbers_plot_02_catalan_numbers.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_02_catalan_numbers.ipynb <plot_02_catalan_numbers.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_02_catalan_numbers.py <plot_02_catalan_numbers.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_02_catalan_numbers.zip <plot_02_catalan_numbers.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_