The Combinatorial Object Server

Object type | |

String length $n$ | (max. 20) |

Alphabet size $k$ | |

Fixed density | (between 0 and $n$) |

Fixed content | (e.g. 5 2 when $n=7$ and $k=2$) |

Forbidden substring | (e.g. 0 0 1) |

Output format | |

Output
numbering
graphics

A necklace is an equivalence class of $k$-ary strings under rotation. We take the lexicographically smallest such string as the representative of each equivalence class and use this in the output of the program.
A Lyndon word is an aperiodic necklace representative.
Unlabelled necklaces are an equivalence classes of necklaces under permutation of alphabet symbols. Note that by permuting the alphabet symbols of a necklace and then rotating the string into its lexicographically smallest position, the result is a necklace representative.
Among all permutations of alphabet symbols that resulting necklace that is lexicographically smallest is used as the representative of an unlabelled necklace.
For example, here is an equivalence class of unlabelled ternary necklaces: $\{011222, 022111, 001112, 002221, 000122, 000211\}$. The lexicographically smallest of these is $000122$ and so it is chosen as the representative.
For information on generating necklaces and Lyndon words and their unlabeled counterparts in constant amortized time see [CRS+00].

In many applications not all necklaces are required, but only those of fixed density, meaning that the number of non-zero entries is fixed. In the more general case, one may want a list of necklaces with fixed content where the number of occurrences for every character is fixed. For information on generating necklaces with fixed content and fixed density in constant amortized time see [Saw03] and [RS99]. Necklaces that do not contain a specified sequence as a substring are known as necklaces with forbidden substrings. For example, when considering all necklaces with $n=4$ and $k=2$ with the restriction that there are no $00$ substrings we get the set: $\{0101, 0111 ,1111\}$. Notice that this is precisely the set of necklaces that start with $0^i$ where $i$ is less than $t$. For more information on generating necklaces with forbidden substrings see [RS00].

A bracelet is a necklace that can be turned over. For information on generating bracelets in constant amortized time see [Saw01]. For bracelets with fixed content see [KSAH13]. The number of nonisomorphic unit interval graphs is the same as the number of binary bracelets of length $2t-1$ with content $(t,t-1)$. A charm bracelet is a generalization of a bracelet considering the action of the group of affine transformations $j \mapsto a+dj\pmod n$ on the indices. For more information see [ĐKRS15].

A chord diagram is a set of $2n$ points on an oriented circle (counterclockwise) joined pairwise by $n$ chords. For information on efficiently generating all chord diagrams with $n$ chords see [Saw02]. We encode such a diagram by walking around the circle, and for each point we record the number of forward steps (in counterclockwise direction) to reach its partner along the same chord. For instance, for $n=3$ the diagram with three chords on the convex hull is encoded by 151515.

Lyndon brackets correspond to the basis of the $n$th homogeneous component of the free Lie algebra. For information on generating such a basis in $O(n)$ time per element see [SR03].

Links to the binary objects in the Online Encyclopedia of Integer Sequences:

- Necklaces: OEIS A000031
- Lyndon words: OEIS A001037
- Bracelets: OEIS A000029
- Lyndon bracelets: OEIS A001371
- Unlabeled necklaces: OEIS A000013
- Unlabeled Lyndon words: OEIS A000048
- Charm bracelets: OEIS A002729
- Chord diagrams: OEIS A007769
- Necklaces with forbidden $00$: OEIS A000358

- [CRS+00] K. Cattell, F. Ruskey, J. Sawada, M. Serra, and C. R. Miers. Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2). J. Algorithms, 37(2):267–282, 2000.
- [ĐKRS15] D. Ž. Đoković, I. Kotsireas, D. Recoskie, and J. Sawada. Charm bracelets and their application to the construction of periodic Golay pairs. Discrete Appl. Math., 188:32–40, 2015.
- [KSAH13] S. Karim, J. Sawada, Z. Alamgir, and S. M. Husnine. Generating bracelets with fixed content. Theoret. Comput. Sci., 475:103–112, 2013.
- [RS99] F. Ruskey and J. Sawada. An efficient algorithm for generating necklaces with fixed density. SIAM J. Comput., 29(2):671–684, 1999.
- [RS00] F. Ruskey and J. Sawada. Generating necklaces and strings with forbidden substrings. In Computing and combinatorics (Sydney, 2000), volume 1858 of Lecture Notes in Comput. Sci., pages 330–339. Springer, Berlin, 2000.
- [Saw01] J. Sawada. Generating bracelets in constant amortized time. SIAM J. Comput., 31(1):259–268, 2001.
- [Saw02] J. Sawada. A fast algorithm for generating nonisomorphic chord diagrams. SIAM J. Discrete Math., 15(4):546–561, 2002.
- [Saw03] J. Sawada. A fast algorithm to generate necklaces with fixed content. Theoret. Comput. Sci., 301(1-3):477–489, 2003.
- [SR03] J. Sawada and F. Ruskey. Generating Lyndon brackets. J. Algorithms, 46(1):21–26, 2003.