Is there any relationship between disorder of a permutation and order of a permutation?
Relationship between disorder of a permutation and order of a permutation
-
0You might want to define what the "disorder of a permutation" is. – 2012-08-17
2 Answers
Emeric Deutsch said at OEIS A008302
The disorder of a permutation $p$ of $(1,2,\ldots ,n)$ is defined in the following manner. We scan $p$ from left to right as often as necessary until all its elements are removed in increasing order, scoring one point for each occasion on which an element is passed over and not removed. The disorder of $p$ is the number of points scored by the end of the scanning and removal process. For example, the disorder of $(3,5,2,1,4)$ is $8$, since on the first scan, $3$, $5$, $2$ and $4$ are passed over, on the second, $3$, $5$ and $4$ and on the third scan, $5$ is once again not removed.
That suggests that the disorder is calculated from the order. Is that what you are looking for?
-
1Deutsch published a Monthly problem on this topic. Here's the JSTOR link: http://www.jstor.org/stable/4145088 – 2017-04-27
I've defined the disorder in my comment on Henry's answer. (EDIT: this is the way it is defined in Section 2.13 of Chris Cooper's notes.) If the disorder is zero then $p$ is the identity, order $1$. If the disorder is $1$ then $p$ is a transposition, in fact, a transposition of the form $(a\quad a+1)$, so of order $2$. But if the disorder is $2$ then $p$ could be $(a\quad a+1)(b\quad b+1)$ of order $2$ or $(a\quad a+1\quad a+2)$ of order $3$. The disorder can be high even if the order is $2$ (use $(1\quad n)$), and fairly low even if the order is high (e.g. $(1\quad2)(3\quad4\quad5)(6\quad7\quad8\quad9\quad10)$ has disorder $7$ and order $30$). In short, I don't think you can say very much about either number based solely on knowledge of the other.