%I
%S 1,2,5,15,47,159,543,1931,6879,25118
%N Maximum probability of permutation from bad "shuffle" times n^n
%C 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].
%C This "shuffle" results in a very nonuniform distribution.
%C The probability of each permutation will be divisible by n^n (because there are n^n possible choices for the random draws).
%C 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] = (n1)/2 or (n+1)/2 results in two equally likely permutations.
%C Empirically the least likely permutation is n,1,2,...n1, with probability 2^(n1)/n^n.
%e 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.
%e For n=3, permutations arise from sequences of j as follows:
%e 1,2,3: j=1,2,3; j=1,3,2; j=2,1,3; j=3,2,1 for probability 4/27
%e 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
%e 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
%e 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
%e 3,1,2: j=1,1,1; j=2,2,1; j=3,2,2; j=3,3,3 for probability 4/27
%e 3,2,1: j=1,2,1; j=2,1,1; j=3,2,3; j=3,3,2 for probability 4/27
%e For n=8, the most likely permutation is 2,3,4,1,6,7,8,5 with probability 1931/8^8
%K nonn,more
%O 1,2
%A _David Applegate_, Jun 21 2011
