numbers (version 0.8-5)

necklace: Necklace and Bracelet Functions

Description

Necklace and bracelet problems in combinatorics.

Usage

necklace(k, n)
bracelet(k, n)

Value

Returns the number of necklaces resp. bracelets.

Arguments

k

The size of the set or alphabet to choose from.

n

the length of the necklace or bracelet.

Details

A necklace is a closed string of length n over a set of size k (numbers, characters, clors, etc.), where all rotations are taken as equivalent. A bracelet is a necklace where strings may also be equivalent under reflections.

Polya's enumeration theorem can be utilized to enumerate all necklaces or bracelets. The final calculation involves Euler's Phi or totient function, in this package implemented as eulersPhi.

References

https://en.wikipedia.org/wiki/Necklace_(combinatorics)

Examples

necklace(2, 5)
necklace(3, 6)

bracelet(2, 5)
bracelet(3, 6)