Necklace (combinatorics)

From Wikipedia, the free encyclopedia

In combinatorics, a k-ary necklace of length n is the equivalence class of all n-character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads of k different colors. Also called fixed necklace to distinguish it from a free necklace, which is an alternate name for a bracelet.

There are

N_k(n)={1\over n}\sum_{d\,|\,n}\varphi\left({n \over d}\right)k^d

different k-ary necklaces of length n, where φ is the Euler's totient function.

[edit] Moreau's necklace-counting function

An aperiodic necklace is an equivalence class, whose elements are all distinct, i.e. no two rotations of the string are equal. According to Moreau's necklace-counting function, there are

M_k(n)={1\over n}\sum_{d\,|\,n}\mu\left({n \over d}\right)k^d

different k-ary aperiodic necklaces of length n, where μ is the Möbius function. Each aperiodic necklace corresponds to a Lyndon word taken from its class.

[edit] External links