The permutations I'm looking at are 2341, 2413, 3412, 3421, 4123 and 4312.

I'll explain the property with the example 2413: I start with the first digit (2) and go to the position 2. There I see the digit 4, so I go to the position 4, there is a 3, so I go to the position 3, there is a 1, so I go to the start. With this, I created a cycle 12431 and visited every position.

3412 is not a permutation, because we only get the cycle 131, so we didn't visited the positions 2 and 4.

Is there a name for these permutations?

  • 2
    $\begingroup$ They are called four-cycles in $S_4$, the permutations of $\{1,2,3,4\}$. Look up "cycle decomposition" and "cycles of a permutation" (suggestion). $\endgroup$ – coffeemath Nov 16 '13 at 12:57
  • $\begingroup$ @coffeemath Would you mind fleshing out your comment into an answer so that this question is no longer "unanswered"? $\endgroup$ – Mark S. Dec 14 '13 at 21:28

The description you give is that you start at some digit between $1$ and $4$ and go from that digit to another one, and so on, not repeating a digit until the last step at which you return to the starting digit. As a function $f$ from the set $S=\{1,2,3,4\}$ to itself, this means that if your starting number is $a$, then the sequence $[a,f(a),f(f(a)),f(f(f(a)))]$ is all four numbers with no repeats, and that one more iteration of $f$ brings you back to the starting $a$, i.e. $f(f(f(f(a))))=a$. These are usually called "4-cycles" of the group $S_4$ of all permutations of the set $S$ mentioned above.

The notation often used is to place the sequence of values inside parentheses, and that's called a "cycle". It's a different way to denote a permutation than the list method. For example your case of $2341$ meaning $1\to 2\to 3 \to 4 \to 1$ is in cycle notation $(1,2,3,4)$, and in any cycle each term inside the cycle maps to the one to its right, with the final term mapping back to the first term of the cycle. Your next list $2413$ which means $1\to 2,2\to 4, 3 \to 1, 4 \to 3$ would then in cycle notation be $(1,2,4,3)$. Note that if all the numbers in the cycle are less than $10$ one can drop the commas between them and write e.g. $(1243).$

Another detail is that a given cycle can be rewritten with any of its terms at the beginning, by shuffling the other terms. For example $$(1243)=(2431)=(4312)=(3124).$$ Each of these cycles has the same effect on each entry.

A single cycle is called an $n$-cycle provided it has $n$ entries in this notation. An $n$ cycle is assumed itself not to move any terms not mentioned in it. They can be combined (composition) to give any permutation, for example $(1,2) \circ (3,4)$ which is not of the 4-cycle type you discuss, but rather a product of two 2-cycles, and still is a permutation of $S$. There's much more to say about this topic, look up "cycle decomposition" for example.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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