0
$\begingroup$

I'm new to mathoverflow but hopefully anyone here can point me in the right direction.

The problem is as follows, imagine you have 4 beads, lets give them numbers 1,2,3,4. Now I want the unique necklaces without rotation, mirror nor duplication of the beads. So 1234 is the same as 3412 and 4321.

How do you call this sequence mathematically? It is related to a free necklace and to bracelet, but those include duplicate use of beads.

For N=1: 1
For N=2: 12 (same as 21)
For N=3: 123 (same as 132,231,213,321,312)
For N=4: 1234 1243 1324 (so not 1342 1423 1432, those are equal flipped)

Is there a good mathematical term for this set? And second: Is there a good way to construct the set for a given number?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What you are doing is enumerating the cosets $\Sigma_N/H$, where $\Sigma_N$ is the group of permutations on $N$ letters and $H$ is the subgroup generated by cyclic permutations and reflection. I don't know of a name for this. (I also think this question would be a better fit for math.stackexchange.com.) $\endgroup$
    – Mark Grant
    Aug 18, 2014 at 12:11
  • $\begingroup$ Regarding math.stackexchange.com, this site was the first that came up on Google and seemed relevant. It isn't entirely clear which questions are appropriate on which exchange, but thanks for the tip. $\endgroup$
    – Roy van Rijn
    Aug 18, 2014 at 13:30
  • 1
    $\begingroup$ MO is for "research level" mathematics, and MSE is for mathematics of all levels. Of course, it's open to interpretation what "research level" means (and it certainly means different things to different people). Anyway, lots of very competent mathematicians answer questions at MSE, and questions such as yours might get a better reception there. (Although it looks like you might already have an answer here). $\endgroup$
    – Mark Grant
    Aug 18, 2014 at 13:55

2 Answers 2

Reset to default
1
$\begingroup$

I don't know the name for this set, but it seems straightforward to generate it. In each equivalence class there is a unique representative starting with "1", and such that either the position of "2" is less than $\frac{N+2}{2}$, or it is equal to $\frac{N+2}{2}$ and the position of "3" is less than $\frac{N+2}{2}$. You just have to generate all the permutations of $(1,\dots,N)$ subject to these conditions.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ I don't ask you to share my sense of elegance, but I'd rather describe the beads as permutations of $(1,\dots,N-1)$ where "1" appears before "2". $\endgroup$
    – Joonas Ilmavirta
    Aug 18, 2014 at 13:06
  • $\begingroup$ @JoonasIlmavirta yep, it is even simpler indeed. $\endgroup$
    – Kostya_I
    Aug 18, 2014 at 13:11
  • $\begingroup$ Is that true? All permutations are: 1234 1243 1324 1342 1423 1432 But some are equal flipped/reversed, e.g. 1234 and 1432. Those shouldn't be in the set. $\endgroup$
    – Roy van Rijn
    Aug 18, 2014 at 13:34
  • $\begingroup$ Of 1234 and 1432, only 1234 satisfies the condition that the position of 2 is less than $\frac{N+2}{2}=3$. So only 1234 will be generated. $\endgroup$
    – Kostya_I
    Aug 18, 2014 at 13:38
  • $\begingroup$ Or: Position 1=1, position 2 < position N, enumerate all? This always forces a direction on the enumerations, making sure no duplicates are present, no cycles due to a fixed starting position. $\endgroup$
    – Roy van Rijn
    Aug 18, 2014 at 13:43
2
$\begingroup$

Terminology: Hamilton cycle

After some searching it turns what I've described above is called the undirected Hamilton cycle (see: http://en.wikipedia.org/wiki/Hamiltonian_path). This page also tells me the amount of bracelets to generate is: $\frac{(N−1)!}{2}$

(but that was already answered by @JoonasIlmavirta and @Kostya_I)

Improve this answer
$\endgroup$
1
  • $\begingroup$ An undirected Hamilton cycle in the complete graph $K_n.$ $\endgroup$
    – Aaron Meyerowitz
    Aug 19, 2014 at 4:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.