.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/abstract_algebra/actions/plot_01_burnside_necklaces.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_abstract_algebra_actions_plot_01_burnside_necklaces.py>`
        to download the full example code.

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

.. _sphx_glr_api_gallery_abstract_algebra_actions_plot_01_burnside_necklaces.py:


Burnside's lemma: counting necklaces
==========================================

Counts two-colored necklaces (up to rotation) and bracelets (up to
rotation and reflection) by averaging fixed points, and checks each
count against direct orbit enumeration.

.. GENERATED FROM PYTHON SOURCE LINES 11-17

.. code-block:: Python

    from itertools import product

    import matplotlib.pyplot as plt

    from mathematicskit.abstract_algebra import CyclicGroup, DihedralGroup, count_orbits, orbits








.. GENERATED FROM PYTHON SOURCE LINES 18-20

Necklaces and bracelets of n beads
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 20-32

.. code-block:: Python


    sizes = range(3, 10)
    necklaces, bracelets = [], []
    for n in sizes:
        words = [tuple(w) for w in product((0, 1), repeat=n)]
        rotate = lambda g, w: w[g:] + w[:g]  # noqa: E731
        permute = lambda g, w: tuple(w[g.index(i)] for i in range(len(w)))  # noqa: E731
        necklaces.append(count_orbits(CyclicGroup(n), words, rotate))
        bracelets.append(count_orbits(DihedralGroup(n), words, permute))
        assert necklaces[-1] == len(orbits(CyclicGroup(n), words, rotate))
        print(f"n = {n}: {2**n} colorings, {necklaces[-1]} necklaces, {bracelets[-1]} bracelets")





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

 .. code-block:: none

    n = 3: 8 colorings, 4 necklaces, 4 bracelets
    n = 4: 16 colorings, 6 necklaces, 6 bracelets
    n = 5: 32 colorings, 8 necklaces, 8 bracelets
    n = 6: 64 colorings, 14 necklaces, 13 bracelets
    n = 7: 128 colorings, 20 necklaces, 18 bracelets
    n = 8: 256 colorings, 36 necklaces, 30 bracelets
    n = 9: 512 colorings, 60 necklaces, 46 bracelets




.. GENERATED FROM PYTHON SOURCE LINES 33-35

Orbit counts grow like 2^n / n
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 35-44

.. code-block:: Python


    fig, ax = plt.subplots()
    ax.semilogy(list(sizes), [2**n for n in sizes], "o-", label="colorings $2^n$")
    ax.semilogy(list(sizes), necklaces, "s-", label="necklaces (rotations)")
    ax.semilogy(list(sizes), bracelets, "^-", label="bracelets (rotations + flips)")
    ax.set_xlabel("number of beads n")
    ax.set_ylabel("count")
    ax.legend()
    ax.set_title("Burnside's lemma")



.. image-sg:: /api/gallery/abstract_algebra/actions/images/sphx_glr_plot_01_burnside_necklaces_001.png
   :alt: Burnside's lemma
   :srcset: /api/gallery/abstract_algebra/actions/images/sphx_glr_plot_01_burnside_necklaces_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none


    Text(0.5, 1.0, "Burnside's lemma")




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

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


.. _sphx_glr_download_api_gallery_abstract_algebra_actions_plot_01_burnside_necklaces.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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