'Mixing number' of permutations
Brendan McKay
bdm at cs.anu.edu.au
Thu Aug 17 15:18:08 CEST 2006
The average is sum(1/binomial(n,k),k=1..n-1). I don't know
if this has a closed form or a name.
Proof: There are clearly k! (n-k)! permutations that have a
break after the k-th value, so the probability of a break in
that place is 1/binomial(n,k).
Asymptotically, the values k=1 and k=n-1 dominate, so the
expectation is 2/n + O(1/n^2).
Brendan.
* Hugo Pfoertner <all at abouthugo.de> [060817 22:30]:
> SeqFans,
>
> today Hauke Reddmann started a new thread in the NG sci.math
>
> http://groups.google.com/group/sci.math/msg/b1c1164b936c6dca
>
> <<
> 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
> --
> Hauke Reddmann <:-EX8 fc3a501 at uni-hamburg.de
> His-Ala-Sec-Lys-Glu Arg-Glu-Asp-Asp-Met-Ala-Asn-Asn
> >>
>
> Is there anything in the OEIS that can answer his question? Any other
> ideas?
>
> Can you please CC answers also to Hauke; AFAIK he is not member of the
> Seqfan community.
>
> Hugo Pfoertner
More information about the SeqFan
mailing list