login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A192053 Maximum probability of permutation from bad "shuffle" times n^n 0
1, 2, 5, 15, 47, 159, 543, 1931, 6879, 25118 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Consider the "shuffle": start with p[i]=i for i in 1..n.  Then, for i in 1..n, pick j uniformly at random from 1..n, and swap p[i] and p[j].

This "shuffle" results in a very non-uniform distribution.

The probability of each permutation will be divisible by n^n (because there are n^n possible choices for the random draws).

Empirically the most likely permutation is 2,3,...,[n/2],1,[n/2]+2,[n/2]+3,...,n,[n/2]+1, with probability a(n)/n^n.  For n odd, taking [n/2] = (n-1)/2 or (n+1)/2 results in two equally likely permutations.

Empirically the least likely permutation is n,1,2,...n-1, with probability 2^(n-1)/n^n.

LINKS

Table of n, a(n) for n=1..10.

EXAMPLE

The sequence of random j values chosen determines the permutation.  For example, for n=3, the sequence j=3,1,3 results in swap(p[1],p[3]), swap(p[2],p[1]), swap(p[3],p[3]), and hence in permutation 2,3,1.

For n=3, permutations arise from sequences of j as follows:

1,2,3: j=1,2,3; j=1,3,2; j=2,1,3; j=3,2,1 for probability 4/27

1,3,2: j=1,2,2; j=1,3,3; j=2,1,2; j=2,3,1; j=3,1,1 for probability 5/27

2,1,3: j=1,1,3; j=2,2,3; j=2,3,2; j=3,1,2; j=3,3,1 for probability 5/27

2,3,1: j=1,1,2; j=1,3,1; j=2,2,2; j=2,3,3; j=3,1,3 for probability 5/27

3,1,2: j=1,1,1; j=2,2,1; j=3,2,2; j=3,3,3 for probability 4/27

3,2,1: j=1,2,1; j=2,1,1; j=3,2,3; j=3,3,2 for probability 4/27

For n=8, the most likely permutation is 2,3,4,1,6,7,8,5 with probability 1931/8^8

CROSSREFS

Sequence in context: A149921 A149922 A013560 * A149923 A219231 A149924

Adjacent sequences:  A192050 A192051 A192052 * A192054 A192055 A192056

KEYWORD

nonn,more

AUTHOR

David Applegate, Jun 21 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 30 14:46 EDT 2020. Contains 337439 sequences. (Running on oeis4.)