Permutation Loops- successor operation

In summary, the conversation discusses a topic in combinatorics related to discrete mathematics and sets. The page in question poorly describes the successor operation, which is a loop formed by a sequence of elements. The example provided shows that the first sequence of elements is equal to A, which is represented as a permutation (23). The conversation then goes on to discuss a better notation for these types of permutations and how they relate to group theory. The person asking for help is not familiar with group theory but is able to understand the explanation given.
  • #1
MathematicalPhysicist
Gold Member
4,699
371
in this page I've encountered this topic (it's a topic from combinatorics, so it's relevant to discrete maths with sets and so on [that's my justification to post it here o:) ), anyway from my point of view the page describes poorly the successor operation:
"The resulting
sequence of elements constitutes another loop, which we will call
the "successor" of the original loop."

here's an example of such successor from the webpage:
I = 123 C = 231
A = 132 D = 312
B = 213 E = 321
IDEACB = A
DEACBI = A
EACBID = B
ACBIDE = A
CBIDEA = A
BIDEAC = E
i don't understand why for example the first sequence of elements equals A (or is identical to it), perhaps i missed something from the explanation, anyone care to explain.

btw, here's the page:
http://www.mathpages.com/home/kmath031.htm
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
There is a better notation than this. When they say I = 123, they mean that I sends 1 to 1, 2 to 2, and 3 to 3. If you have X = xyz, then X sends 1 to x, 2 to y, and 3 to z. A more standard notation would be to write it like this:

Code:
X = [1 2 3]
    [x y z]

So X sends whatever is in the top row to the thing directly above it. So in particular, we have:

Code:
A = [1 2 3]
    [1 3 2]

A basically just swaps 2 and 3. This is commonly denoted as (23). We will use this notation from now on. X = (xy) means that it sends x to y, y to x, and leaves z fixed. X' = (x'y'z') means that it sends x' to y', y' to z', and z' to y'. We can denote I as (), since it does nothing.

Now, if you have something like:

(123)(23)(23)(132)(231)(12)(321)

then you read it from right to left. The right-most one sends 1 to 3. The next one leaves 3 fixed. The next one sends 3 to 1, and then 1 to 3, 3 to 2, 2 to 3, and finally 3 to 1, so this whole thing sends 1 to 1. Next, look at 2. The right most one sends 2 to 1, then the next one sends 1 to 2, the next one sends 2 to 3, then 3 to 2, then 2 to 3, then 3 to 2, then 2 to 3, so this whole thing sends 2 to 3. Obviously, it sends 3 to 2, so we get:

(123)(23)(23)(132)(231)(12)(321) = (23) = (32)

Note that (23) and (32) are the same. However, given your original notation, 23 and 32 are not even defined. You should also notice that (123) and (312) are the same, but given your original notation, 123 and 312 are defined but are not equal, since 123 is:

[1 2 3]
[1 2 3]

which is just (), and 312 is:

[1 2 3]
[3 1 2]

which is (132).

IDEACB
= ()(132)(13)(23)(123)(12)
= (23)
= A

as required. See if you can figure out the rest for yourself.
 
  • #3
By the way, I don't think the site did a bad job of explaining things, it seems that you're just unfamiliar with the permuation groups. Do you know what a group is? As far as I can tell, this has much more to do with group theory (part of abstract algebra) and much less to do with combinatorics. There is some relation to the idea of permutations as a group, and permutations where you calculate things like "n arrange k," but from the part of that link that I read, this has much less to do with calculating things like "n arrange k" and more to do with group theory. At very least, it seems to require some knowledge of group theory but no particular knowledge of combinatorics. Maybe further down the page on that link, things are different...
 
  • #4
ok, i understand it, a bit tricky i think but nice. anyway my knowledge on group theory mainly stands on knowledge of the axioms (and when the author did specify accosiativity and identity element it felt as if it's connected to groups), and the simple theorems with the identity element of a group, not a lot i know :blushing:

btw, thanks for the help.
 

1. What is a permutation loop?

A permutation loop is a mathematical concept that involves rearranging a set of elements in a specific order or sequence. It is often used in computer programming and mathematics to solve problems involving combinations and arrangements.

2. What is the successor operation in permutation loops?

The successor operation in permutation loops is a way to generate the next permutation in a loop. It involves finding the smallest element in the current permutation and swapping it with the next larger element, while keeping the remaining elements in the same order.

3. How is the successor operation used in permutation loops?

The successor operation is used in permutation loops to generate all possible permutations of a set of elements. By repeatedly applying the successor operation, the loop can generate all possible combinations of the elements, allowing for efficient problem solving and analysis.

4. Are there any limitations to using permutation loops with the successor operation?

While permutation loops with the successor operation are a powerful tool for solving problems, there are some limitations. As the size of the set of elements increases, the number of possible permutations also increases, making it computationally intensive. Additionally, the successor operation may not work for certain types of elements, such as repeating elements or non-numerical elements.

5. How is the successor operation different from other operations in permutation loops?

The successor operation is unique in that it generates the next permutation in a loop, while keeping the remaining elements in the same order. Other operations, such as swapping two elements or rotating the elements, may change the order of all the elements in the permutation. The successor operation is also essential in generating all possible permutations, while other operations may only generate a subset of permutations.

Similar threads

  • General Math
Replies
2
Views
1K
Replies
3
Views
2K
  • Differential Geometry
Replies
29
Views
1K
Replies
2
Views
2K
  • General Math
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
10
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Beyond the Standard Models
Replies
4
Views
3K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
  • Math Proof Training and Practice
3
Replies
97
Views
18K
Back
Top