The "mixing number" of a permutation
Hauke Reddmann
The finish in terms of the starting numbers was
7 1 6 4 3 8 5 2|9|10|14 15 20 13 18 16 23 22 12 26 11 17 19 27 25 21 24|28
A | marks boundaries between consecutive number subsets that permute
to themselves. Note that I (the 16) also permute to myself, but there
are number crossing from both sides and so this is no boundary.
Obvious question: How many boundaries occur in a random permutation?
Clearly a tournament is about the opposite of random, as the swap
numbers will be low.
Example n=3
1|2|3
1|3 2
2 1|3
2 3 1
3 1 2
3 2 1
--
Hauke Reddmann <:-EX8 fc3...@uni-hamburg.de
His-Ala-Sec-Lys-Glu Arg-Glu-Asp-Asp-Met-Ala-Asn-Asn
Chip Eastham
If there are no fixed elements, aka a derangement, would you have
no boundaries? Consider this arrangement:
2 1 4 3 6 5
Although no element maps to itself, the domain can be partitioned
into three 2-element invariant subdomains.
regards, chip
M.J.T. Guy
>For easyness, I use the data of my lest chess tournament :-)
>The finish in terms of the starting numbers was
>7 1 6 4 3 8 5 2|9|10|14 15 20 13 18 16 23 22 12 26 11 17 19 27 25 21 24|28
>
>A | marks boundaries between consecutive number subsets that permute
>to themselves. Note that I (the 16) also permute to myself, but there
>are number crossing from both sides and so this is no boundary.
>
>Obvious question: How many boundaries occur in a random permutation?
>Clearly a tournament is about the opposite of random, as the swap
>numbers will be low.
>
>Example n=3
>
>1|2|3
>1|3 2
>2 1|3
>2 3 1
>3 1 2
>3 2 1
There is a boundary between k and k+1 exactly if the first k elements
are a permutation of 1..k . There are k!(n-k)! of these, so
the probablity of a boundary at k:k+1 is k!(n-k)!/n! . The expected
number of boundaries is obtained by summing this from k=1 to n-1.
Mike Guy