A necklace is the rotationally-equivalent version of a word on an alphabet. As an example, the two words "$aabaaab$" and "$abaaaba$" are rotations of one another, and represent the same necklace.
Suppose we also want to make equivalent any two words that are related via a simple permutation of the alphabet. As an example, we want to equate the words "$aabaaab$" and "$bbabbba$", which are related by switching $a$ and $b$.
(Necklaces sometimes refer to the alphabet symbols as "colors," so we can also say we are permuting the "colors".)
If we do this, and if we also keep rotational equivalence, we then get a union of necklaces. As an example, if the alphabet is just "a" and "b", the following is the set of all equivalent strings:
$$ \{aabaaab, abaaaba, baaabaa, aaabaab, aabaaba, abaabaa, baabaaa, \\ bbabbba, babbbab, abbbabb, bbbabba, bbabbab, babbabb, abbabbb \} $$
Questions:
- Do these "alphabet-permutationally-invariant necklaces" have a name?
- Is there a simple unique representation for any such permutationally-invariant necklace?
- Does the terminology change if "reflection" is also permitted, i.e. the palindrome of a string is also viewed as equivalent?
A necklace of length $n$ with an alphabet of size $k$ can be thought of as an orbit of the cyclic group $C_n$ (the group of ways to rotate the necklace) acting on the set of $n$ character strings. (see here for more details)
A 'reflectionally-invariant necklace' is called a 'bracelet'. Alternatively, you could call it an orbit of the dihedral group $D_n$ (the group of ways to rotate or reflect the necklace) acting on the set of $n$ character strings.
A 'permutationally-invariant necklace' or 'unlabelled necklace' is an orbit of the group of ways to rotate the necklace or permute its alphabet acting on the set of $n$ character strings.