Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you have n beads on a string, the beads are labeled 1,2,3,...,n. How many possible permutations are there if you are allowed to flip the string over?

E.g. For 4 beads, 1--2--3--4 is equivalent to 4--3--2--1.

Attempt

Without considering the "flip the string" condition, the total number of permutations is $n!$.

Based on trying out small examples, I think half of those are equivalent to "flipping over the string". So the answer is $n!/2$.

Question

Am I right and how can I show this?

Edit

The string is not a loop.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

You basically have it. For each string of beads, there are two possible permutations you can create (because you can start at either end of the string). Conversely, for every possible permutation, there is a unique string of beads that you can make which will produce that permutation. So if $N$ represents the number of possible strings of beads and $n!$ represents the number of possible permutations, you have shown that $2 N = n!$, so $N = \frac{n!}{2}$.

Edit: This is an attempt to make the argument clearer. You have a function which maps the set of all permutations of $1,2,\dots,n$ to the set of all strings of $n$ beads (the beads numbered $1,2,\dots,n$). Given a permutation $a_1 a_2 \cdots a_n$ (i.e. $a_i$ is the $i^{\text{th}}$ number in the permutation), then make a string of beads in the order $a_1, a_2, \dots, a_n$. This is a surjective function (for every string of beads, there is some permutation corresponding to it). In fact the preimage of any string of beads consists of two permutations since you either read the beads from left to right or right to left. Thus, you have a $2$-to-$1$ function from a set with $n!$ elements. The image set therefore has cardinality $n!/2$.

share|improve this answer
    
Do you mind making your answer clearer? Not really seeing it. :) –  Legendre Sep 28 '12 at 20:06
    
Is the second explanation any better? If not, could you specify the first statement in the argument that is giving you trouble. –  Michael Joyce Sep 28 '12 at 21:35
1  
Got it now. Thanks. I suppose we could say every string corresponds to exactly 2 permutations. And these 2 permutations both correspond to only this 1 string. –  Legendre Sep 29 '12 at 11:52

Your answer is almost correct.

If $n>1$ then flipping reduces the possible strings by half and the answer is $\frac{n!}2$. This is so because no string can possibly be symmetric with respect to flipping (and hence flipping goups all sequences in groups of two): The first number differs from the last number, which becomes first number by flipping.

However, if $n\le1$, then all strings of length $n$ are "flip-symmetric", hence do halfing occurs.

In summary

$$f(n) = \begin{cases}\tfrac{n!}2&\mathrm{if\ }n\ge 2\\ 1&\mathrm{if\ }n\in\{0,1\}\end{cases}$$

share|improve this answer
    
+1. Thanks for catching that. –  Legendre Sep 29 '12 at 11:53

If the $n$ beads sat in a row, then there would be $n!$ arrangements. Once you clasp the ends and allow rotations, you must divide by the number of possible rotations: $n!/n=(n-1)!$. Finally, the flip allows to two additional symmetries: $(n-1)!/2$.

Alternatively, note $D_n$ acts on the object...

share|improve this answer
    
The problem doesn't specify that the string is a loop. If it is, then your solution is correct. But Legendre is correct if the string does not have its ends tied together. –  Michael Joyce Sep 28 '12 at 19:41
    
@MichaelJoyce - Right. The string isn't a loop. I will make that clear in my question. Thanks to the both of you! –  Legendre Sep 28 '12 at 19:44
    
Oops. Just logged back in and noted that I answered the wrong question. Rotations aside, the reflective symmetries part still applies and hence provides the desired solution $n!/2$ for the $n$-bead case. –  NoClue Sep 30 '12 at 21:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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