2
$\begingroup$

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.

3 Answers 3

2

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$.

  • 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.2012-09-29
2

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}$

1

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...

  • 0
    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.2012-09-30