Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 NecklaceCount

Source Notebook

Count the number of distinct necklaces made with beads of different colors

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["NecklaceCount"][group,n]

gives the number of distinct necklaces that can be constructed with beads of n colors using operations defined by group.

Details and Options

ResourceFunction["NecklaceCount"] uses the Pólya enumeration theorem.
Possible values of group are CyclicGroup[n] and DihedralGroup[n], with positive integer values of the number of beads n.
Two necklace colorings are assumed to be equivalent if one can be obtained from the other by a rotation for the cyclic group and rotation or flip for the dihedral group .
Necklaces produced by the cyclic group are also called "fixed necklaces" to distinguish them from "turnover necklaces" or "bracelets" produced by the dihedral group.

Examples

Basic Examples (2) 

The number of distinct (fixed) necklaces of six beads in three colors:

In[1]:=
ResourceFunction["NecklaceCount"][CyclicGroup[6], 3]
Out[1]=

The number of bracelets of five beads in two colors:

In[2]:=
ResourceFunction["NecklaceCount"][DihedralGroup[5], 2]
Out[2]=

Properties and Relations (2) 

The necklace count can be obtained from CycleIndexPolynomial for the corresponding group:

In[3]:=
npoly = CycleIndexPolynomial[CyclicGroup[6], Array[Subscript[a, ##] &, 6]]
Out[3]=
In[4]:=
npoly /. Subscript[a, i_] -> r^i + g^i + b^i /. {r -> 1, g -> 1, b -> 1}
Out[4]=
In[5]:=
ResourceFunction["NecklaceCount"][CyclicGroup[6], 3]
Out[5]=

Or for a bracelet:

In[6]:=
bpoly = CycleIndexPolynomial[DihedralGroup[5], Array[Subscript[a, ##] &, 5]]
Out[6]=
In[7]:=
bpoly /. Subscript[a, i_] -> b^i + w^i /. {b -> 1, w -> 1}
Out[7]=

Version History

  • 1.0.0 – 23 June 2020

Related Resources

License Information