:orphan:

Examples
========

This gallery walks through every public feature of ``mathematicskit.combinatorics``:
permutation/combination counting and generation, Pascal's triangle,
integer partitions, the inclusion-exclusion principle, and Stirling/
Catalan/Bell numbers.

See also the narrative tutorial:

- :doc:`/tutorials/counting_primes_and_probability`

Each script in this gallery is self-contained and can be run directly with
``python examples/combinatorics/<section>/<script>.py``.

Sections
--------

- **counting** -- permutation/combination counting and sequence
  generation, and multinomial coefficients.
- **pascals_triangle** -- the binomial-coefficient recurrence.
- **partitions** -- the partition function, enumeration, and Young
  diagrams.
- **inclusion_exclusion** -- the inclusion-exclusion principle and
  derangements.
- **special_numbers** -- Stirling numbers, Catalan numbers, and Bell
  numbers.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. thumbnail-parent-div-close

.. raw:: html

    </div>

Counting
----------

Permutation/combination counting and generation, and multinomial
coefficients.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Counts 5-card poker hands and a few hand types, and cross-checks the count against brute-force enumeration for a smaller deck.">

.. only:: html

  .. image:: /api/gallery/combinatorics/counting/images/thumb/sphx_glr_plot_01_poker_hands_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/counting/plot_01_poker_hands`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Counting poker hands</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Levi ben Gershon&#x27;s 1321 Maaseh Hoshev proved by induction that n objects can be arranged in n! orders, that k of them can be arranged in n!/(n-k)! ways, and that k can be chosen in n!/(k!(n-k)!) ways. This example checks each formula against brute-force enumeration.">

.. only:: html

  .. image:: /api/gallery/combinatorics/counting/images/thumb/sphx_glr_plot_02_gersonides_formulas_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/counting/plot_02_gersonides_formulas`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Gersonides' counting formulas</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Combinatorial designs
---------------------

Latin squares and orthogonal pairs.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Builds a pair of orthogonal Latin squares of order 5 and superimposes them so that every (rank, regiment) pair appears exactly once, the arrangement Euler&#x27;s 36-officers problem asks for. It then checks by brute force that no such pair exists for order 2.">

.. only:: html

  .. image:: /api/gallery/combinatorics/designs/images/thumb/sphx_glr_plot_01_latin_squares_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/designs/plot_01_latin_squares`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Euler's officers: orthogonal Latin squares</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Extremal combinatorics
----------------------

Ramsey's theorem and the Erdős-Szekeres theorem: order that must appear
in any large enough structure.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Searches every red/blue coloring of the edges of K_5 and K_6. K_5 has colorings with no single-colored triangle, such as the pentagon and pentagram, but every one of the 32768 colorings of K_6 contains one.">

.. only:: html

  .. image:: /api/gallery/combinatorics/extremal/images/thumb/sphx_glr_plot_01_ramsey_r33_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/extremal/plot_01_ramsey_r33`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Ramsey's theorem: R(3,3) = 6</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Any sequence of (r-1)(s-1)+1 distinct numbers contains an increasing subsequence of length r or a decreasing one of length s. This example finds the longest monotone subsequences of random permutations and shows that their length grows like 2 sqrt(n).">

.. only:: html

  .. image:: /api/gallery/combinatorics/extremal/images/thumb/sphx_glr_plot_02_erdos_szekeres_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/extremal/plot_02_erdos_szekeres`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The Erdős-Szekeres theorem: monotone subsequences</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Inclusion-exclusion
---------------------

The inclusion-exclusion principle and derangements.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="n people check their hats and receive one back at random; what&#x27;s the probability nobody gets their own hat back? The answer converges to 1/e remarkably quickly.">

.. only:: html

  .. image:: /api/gallery/combinatorics/inclusion_exclusion/images/thumb/sphx_glr_plot_01_hat_check_problem_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/inclusion_exclusion/plot_01_hat_check_problem`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The hat-check problem: derangements via inclusion-exclusion</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Matchings
---------

Hall's marriage theorem and bipartite matchings.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Checks Hall&#x27;s condition on random bipartite graphs and confirms that it holds exactly when a matching covers every left vertex. When it fails, the example prints the subset whose neighbourhood is too small.">

.. only:: html

  .. image:: /api/gallery/combinatorics/matching/images/thumb/sphx_glr_plot_01_hall_marriage_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/matching/plot_01_hall_marriage`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Hall's marriage theorem</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Necklaces
---------

Pólya enumeration: counting colorings up to symmetry.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Counts necklaces (up to rotation) and bracelets (up to rotation and reflection) with Pólya&#x27;s formula, and draws the 8 distinct two-colored necklaces of 5 beads.">

.. only:: html

  .. image:: /api/gallery/combinatorics/necklaces/images/thumb/sphx_glr_plot_01_polya_necklaces_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/necklaces/plot_01_polya_necklaces`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Pólya's enumeration theorem: necklaces and bracelets</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Integer partitions
--------------------

The partition function, enumeration, and Young diagrams.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Enumerates every partition of 6, checks the count against the partition function p(6), and visualizes one partition&#x27;s Young diagram and its conjugate.">

.. only:: html

  .. image:: /api/gallery/combinatorics/partitions/images/thumb/sphx_glr_plot_01_partitions_and_young_diagrams_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/partitions/plot_01_partitions_and_young_diagrams`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Integer partitions, the partition function, and Young diagrams</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Pascal's triangle
-------------------

The binomial-coefficient recurrence, built by hand.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Builds Pascal&#x27;s triangle by hand via the addition recurrence and confirms every entry matches scipy.special.comb.">

.. only:: html

  .. image:: /api/gallery/combinatorics/pascals_triangle/images/thumb/sphx_glr_plot_01_triangle_and_binomials_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/pascals_triangle/plot_01_triangle_and_binomials`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Pascal's triangle vs. scipy-computed binomial coefficients</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Integer sequences
-----------------

Fibonacci numbers, Bernoulli numbers and sums of powers, and Gray
codes.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Reproduces the rabbit problem from Fibonacci&#x27;s 1202 Liber Abaci, checks that the same numbers count domino tilings of a 2-by-n strip, and shows the ratio of successive terms approaching the golden ratio.">

.. only:: html

  .. image:: /api/gallery/combinatorics/sequences/images/thumb/sphx_glr_plot_01_fibonacci_rabbits_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/sequences/plot_01_fibonacci_rabbits`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Fibonacci's rabbits and domino tilings</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Computes the Bernoulli numbers exactly, uses them to evaluate sums of p-th powers in closed form, and repeats Bernoulli&#x27;s own boast: the sum of the tenth powers of the first 1000 integers.">

.. only:: html

  .. image:: /api/gallery/combinatorics/sequences/images/thumb/sphx_glr_plot_02_bernoulli_power_sums_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/sequences/plot_02_bernoulli_power_sums`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Jacob Bernoulli's numbers and sums of powers</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Lists the reflected binary Gray code, checks that neighbouring codes differ in exactly one bit, and compares the number of bit flips needed to count through all n-bit words with ordinary binary counting.">

.. only:: html

  .. image:: /api/gallery/combinatorics/sequences/images/thumb/sphx_glr_plot_03_gray_code_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/sequences/plot_03_gray_code`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Gray codes: counting one bit at a time</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Special numbers
-----------------

Stirling numbers, Bell numbers, and Catalan numbers.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Checks by brute force that Stirling numbers of the first kind count permutations by their number of cycles and that Stirling numbers of the second kind count partitions of a labeled set into k blocks. It then recovers Stirling&#x27;s own use of them, converting ordinary powers into falling factorials, and sums the second kind to get the Bell numbers.">

.. only:: html

  .. image:: /api/gallery/combinatorics/special_numbers/images/thumb/sphx_glr_plot_01_stirling_numbers_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/special_numbers/plot_01_stirling_numbers`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Stirling's numbers: cycles, set partitions, and Bell numbers</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="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&#x27;s bracketing problem of 1838.">

.. only:: html

  .. image:: /api/gallery/combinatorics/special_numbers/images/thumb/sphx_glr_plot_02_catalan_numbers_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/special_numbers/plot_02_catalan_numbers`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Catalan numbers: Euler's polygon triangulations and Catalan's brackets</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Labeled trees
-------------

Cayley's formula and Prüfer codes.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Encodes labeled trees as Prüfer sequences and decodes every sequence of length n-2 back to a tree. The correspondence is one-to-one, so there are n^(n-2) labeled trees on n vertices.">

.. only:: html

  .. image:: /api/gallery/combinatorics/trees/images/thumb/sphx_glr_plot_01_prufer_codes_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/trees/plot_01_prufer_codes`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Cayley's formula via Prüfer codes</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:
   :includehidden:


   /api/gallery/combinatorics/counting/index.rst
   /api/gallery/combinatorics/designs/index.rst
   /api/gallery/combinatorics/extremal/index.rst
   /api/gallery/combinatorics/inclusion_exclusion/index.rst
   /api/gallery/combinatorics/matching/index.rst
   /api/gallery/combinatorics/necklaces/index.rst
   /api/gallery/combinatorics/partitions/index.rst
   /api/gallery/combinatorics/pascals_triangle/index.rst
   /api/gallery/combinatorics/sequences/index.rst
   /api/gallery/combinatorics/special_numbers/index.rst
   /api/gallery/combinatorics/trees/index.rst



.. only:: html

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

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