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?
-
2How does this suggest the disorder is calculated from the order? – 2011-03-21
-
2This is "abbreviated 2-line notation", I think: that is, "(3,5,2,1,4)" means the permutation that sends 1 to 3, 2 to 5, 3 to 2, 4 to 1, and 5 to 4. Otherwise, if this were "cycle notation", the disorder would depend on the representation: (1,4,3,5,2) is the same cycle permutation as (3,5,2,1,4), but the disorder would be 5. Just thought it might be worth mentioning... – 2011-03-21
-
1I think the disorder of $p=(3,5,2,1,4)$ is $6$, not $8$. We count $(i,j)$ such that $i\lt j$ but $p(i)\gt p(j)$. E.g., $1\lt 3$ but $p(1)=3\gt2=p(3)$ so we count $(1,3)$. We count $(1,3),(1,4),(2,3),(2,4),(2,5),(3,4)$, that's $6$. I doubt there's any simple relation between disorder of $p$ and its order as an element of $S_n$. – 2011-04-21
-
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.