Necklace (combinatorics)

Necklace (combinatorics)

In combinatorics, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads of up to k different colors.

The three bracelets which can be made with 3 red beads and 3 blue beads

A k-ary bracelet, also referred to as a turnover (or free) necklace, is a necklace such that strings may also be equivalent under reflection. That is, given two strings, if each is the reverse of the other then they belong to the same equivalence class. For this reason, a necklace might also be called a fixed necklace to distinguish it from a turnover necklace.

Technically, one may classify a necklace as an orbit of the action of the cyclic group on n-character strings, and a bracelet as an orbit of the dihedral group's action.

Contents

Equivalence classes

Number of necklaces

There are

N_k(n)={1\over n}\sum_{d\mid n}\varphi(d)k^{n/d}

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

Number of bracelets

There are


B_k(n) = 
\begin{cases}
{1\over 2}N_k(n) + {1\over 4}(k+1)k^{n/2} & \text{if }n\text{ is even} \\  \\
{1\over 2}N_k(n) + {1 \over 2}k^{(n+1)/2} & \text{if }n\text{ is odd}
\end{cases}

different k-ary bracelets of length n, where Nk(n) is the number of k-ary necklaces of length n.

Examples

Necklace example

If there are n beads, all unique, on a necklace joined at the ends, then the number of unique orderings on the necklace, after allowing for rotations, is n!/n, for n > 0. This may also be expressed as (n − 1)!. This number is less than the general case, which lacks the requirement that each bead must be unique.

An intuitive justification for this can be given. If there is a line of n unique objects ("beads"), the number of combinations would be n!. If the ends are joined together, the number of combinations are divided by n, as it is possible to rotate the string of n beads into n positions.

Bracelet example

If there are n beads, all unique, on a bracelet joined at the ends, then the number of unique orderings on the bracelet, after allowing for rotations and reflection, is n!/(2n), for n > 2. Note that this number is less than the general case of Bn(n), which lacks the requirement that each bead must be unique.

To explain this, one may begin with the count for a necklace. This number can be further divided by 2, because it is also possible to flip the bracelet over.

Aperiodic necklaces

An aperiodic necklace of length n is an equivalence class of size n, i.e., no two distinct rotations of a necklace from such class are equal.

According to Moreau's necklace-counting function, there are

M_k(n)={1\over n}\sum_{d\mid n}\mu(d)k^{n/d}

different k-ary aperiodic necklaces of length n, where μ is the Möbius function.

Each aperiodic necklace contains a single Lyndon word so that Lyndon words form representatives of aperiodic necklaces.

See also

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Necklace problem — The necklace problem is a problem in recreational mathematics, solved in the early 21st century. Contents 1 Formulation 2 Solution 3 References 4 See also …   Wikipedia

  • Necklace (disambiguation) — A necklace is an article of jewelry worn around the neck. Necklace may also refer to: Necklace (combinatorics) or fixed necklace, a concept in combinatorial mathematics The Necklace , a short story by Guy de Maupassant The Necklace , an episode… …   Wikipedia

  • Combinatorics on words — Construction of a Thue Morse infinite word Combinatorics on words is a branch of mathematics which applies combinatorics to words and formal languages. The study of combinatorics on words arose independently within several branches of mathematics …   Wikipedia

  • Combinatorics — is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size (enumerative combinatorics), deciding when certain criteria can be met,… …   Wikipedia

  • Necklace splitting problem — In mathematics, and in particular combinatorics, the necklace splitting problem arises in a variety of contexts including exact division; its picturesque name is due to mathematicians Noga Alon [1] and Douglas B. West.[2] Suppose a necklace, open …   Wikipedia

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

  • Necklace polynomial — In combinatorial mathematics, the necklace polynomials, or (Moreau s) necklace counting function are the polynomials M(α,n) in α such that By Möbius inversion they are given by where μ is the classic Möbius function. The necklace polynomials are… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • Topological combinatorics — The discipline of combinatorial topology used combinatorial concepts in topology and in the early 20th century this gradually turned into the field of algebraic topology. In 1978 the situation was reversed when methods from algebraic topology… …   Wikipedia

  • Bracelet (combinatorics) — In combinatorics, a k ary bracelet of length n is the equivalence class of all n character strings over an alphabet of size k , taking reverse and all rotations as equivalent. A bracelet, also referred to as a turnover necklace, represents a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”