|
|
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, ..., floor(n/2), 1, floor(n/2)+2, floor(n/2)+3, ..., n, floor(n/2)+1, with probability a(n)/n^n. For n odd, taking floor(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.
The first empirical observation is known to be false, see Proposition 2.9 of Schmidt and Simion. Therefore, a(n) > A013560(n) for sufficiently large n. - Sean A. Irvine, Mar 29 2022
|
|
|
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 with 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 with 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 with 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 with probability 5/27;
3,1,2: j=1,1,1; j=2,2,1; j=3,2,2; j=3,3,3 with probability 4/27;
3,2,1: j=1,2,1; j=2,1,1; j=3,2,3; j=3,3,2 with probability 4/27.
For n=8, the most likely permutation is 2,3,4,1,6,7,8,5 with probability 1931/8^8.
|
