Cyclic order: Difference between revisions
Jump to navigation
Jump to search
imported>John R. Brews (→Examples: reverse cyclic order) |
imported>John R. Brews (→Examples: acyclic order) |
||
Line 27: | Line 27: | ||
* (Alice, Bob, Celia, Don), (Bob, Celia, Don, Alice), (Celia, Don, Alice, Bob), and (Don, Alice, Bob, Celia) all describe the same cyclic (seating) order. <br> (Alice, Don, Celia, Bob) describes the reverse cyclic order, and (Alice, Celia, Bob, Don) describes a different cyclic order. | * (Alice, Bob, Celia, Don), (Bob, Celia, Don, Alice), (Celia, Don, Alice, Bob), and (Don, Alice, Bob, Celia) all describe the same cyclic (seating) order. <br> (Alice, Don, Celia, Bob) describes the reverse cyclic order, and (Alice, Celia, Bob, Don) describes a different cyclic order. | ||
* The hours on a clock are in cyclic order: one o'clock follows twelve o'clock. | * The hours on a clock are in cyclic order: one o'clock follows twelve o'clock. The reverse order, (two o'clock, one o'clock, twelve o'clock ... ) is sometimes called ''acyclic'' order. | ||
* All of (123),(231),(312) are in cyclic order. Also, (132),(213),(321) are in cyclic order, but not the same order as the previous set. Because the integers have a natural sequence 1, 2, 3 ..., the second set are sometimes said to be in ''reverse'' cyclic order. | * All of (123),(231),(312) are in cyclic order. Also, (132),(213),(321) are in cyclic order, but not the same order as the previous set. Because the integers have a natural sequence 1, 2, 3 ..., the second set are sometimes said to be in ''reverse'' cyclic order, and sometimes as in ''acyclic'' order. |
Revision as of 09:51, 6 January 2011
The typical example of a cyclic order are people seated at a (round) table: Each person has a right-hand and a left-hand neighbour, and no position is distinguished from the others. The seating order can be described by listing the persons, starting from any arbitrary position, in clockwise (or counterclockwise) order.
Mathematical formulation
The abstract concept analogous to sitting around a table can be described in mathematical terms as follows:
On a finite set S of n elements, consider a function σ that defines for each element s its successor σ(s).
This gives rise to a cyclic order if (and only if) for some element s the orbit under σ is the whole set S:
The reverse cyclic order is given by σ−1 (where σ−1(s) is the element preceding s).
Remarks:
- If the condition holds for one element then it holds for all elements.
- All cyclic orders of n elements are isomorphic.
- Cyclic orders cannot be considered as order relations because both s < t and t < s would hold for any two distinct elements s and t.
- Cyclic orders occur naturally in number theory (residue sets and group theory (cyclic groups, permutations).
Examples
- (Alice, Bob, Celia, Don), (Bob, Celia, Don, Alice), (Celia, Don, Alice, Bob), and (Don, Alice, Bob, Celia) all describe the same cyclic (seating) order.
(Alice, Don, Celia, Bob) describes the reverse cyclic order, and (Alice, Celia, Bob, Don) describes a different cyclic order.
- The hours on a clock are in cyclic order: one o'clock follows twelve o'clock. The reverse order, (two o'clock, one o'clock, twelve o'clock ... ) is sometimes called acyclic order.
- All of (123),(231),(312) are in cyclic order. Also, (132),(213),(321) are in cyclic order, but not the same order as the previous set. Because the integers have a natural sequence 1, 2, 3 ..., the second set are sometimes said to be in reverse cyclic order, and sometimes as in acyclic order.