World Library  
Flag as Inappropriate
Email this Article

Necklace (combinatorics)

Article Id: WHEBN0006226587
Reproduction Date:

Title: Necklace (combinatorics)  
Author: World Heritage Encyclopedia
Language: English
Subject: Necklace problem, Combinatorics on words, Permutation, Necklace (disambiguation), Necklace polynomial
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Necklace (combinatorics)

Possible patterns of bracelets of length n
corresponding to the k-th integer partition
(set partitions up to rotation and reflection)
The 3 bracelets with 3 red and 3 green beads. The one in the middle is chiral, so there are 4 necklaces.
Compare box(6,9) in the triangle.
The 11 bracelets with 2 red, 2 yellow and 2 green beads. The leftmost one and the four rightmost ones are chiral, so there are 16 necklaces.
Compare box(6,7) in the triangle.
16 Tantrix tiles, corresponding to the 16 necklaces with 2 red, 2 yellow and 2 green beads.

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.

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 1
    • Number of necklaces 1.1
    • Number of bracelets 1.2
  • Examples 2
    • Necklace example 2.1
    • Bracelet example 2.2
  • Aperiodic necklaces 3
  • Products of Necklaces 4
  • See also 5
  • References 6
  • External links 7

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.[1]

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 distinct, on a necklace joined at the ends, then the number of distinct 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 distinct.

An intuitive justification for this can be given. If there is a line of n distinct 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 distinct, on a bracelet joined at the ends, then the number of distinct 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 distinct.

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.

Products of Necklaces

The limit of the product of the numbers of fixed necklaces of length n composed of k types of beads:

\lim_{n \to \infty} \prod_{n=1}^n N_k(n)= \frac {k^n} {n!} 1(1+X)(1+X+X^2)\cdots(1+X+X^2+\cdots+X^{n-1}),

where the coefficient of X^k in the expansion of the product

\prod_{m=1}^n\sum_{i=0}^{m-1}X^i=1(1+X)(1+X+X^2)\cdots(1+X+X^2+\cdots+X^{n-1})

presents the number of permutations of n with k inversions, expressed by a Mahonian number: (See Gaichenkov link)

See also

References

  1. ^ http://mathworld.wolfram.com/Necklace.html

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.