Bracelet (combinatorics)

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 structure with "n" circulary connected beads of "k" different colors, which (unlike a necklace) can be turned over.

There are:B_k(n) = egin{cases}{1over 2}N_k(n) + {1over 4}(k+1)k^{n/2} & mbox{if }nmbox{ is even} \ \{1over 2}N_k(n) + {1 over 2}k^{(n+1)/2} & mbox{if }nmbox{ is odd}end{cases}different "k"-ary bracelets of length "n", where N_k(n) is the number of "k"-ary necklaces of length "n".

See also

*Lyndon word

External links

* [http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html Info on necklaces, Lyndon words, De Bruijn sequences]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • 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

  • 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 …   Wikipedia

  • 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

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

Share the article and excerpts

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