Given an ordered string T of unique elements, consider an operation that takes k elements and permutes them randomly.
If you consider all the permutations of T, and you categorize them according to the minimum number of operations required to reach T, how many permutations are in each grouping?
For example, ABC, where an operation is swapping 2 elements:
0 operations: ABC (1 permutation)
1 operation: BAC, CBA, ACB (3 permutations)
2 operations: CAB, BCA (2 permutations)
So we could write this as
Swap 2
- n= 2: 1,3,2
So what do these groupings look like?
Swap 2
- n= 2: 1,1
- n= 3: 1,3,2
- n= 4: 1,6,11,6
- n= 5: 1,10,35,50,24
- n= 6: 1,15,85,225,274,120
- n= 7: 1,21,175,735,1624,1764,720
- n= 8: 1,28,322,1960,6769,13132,13068,5040
h3.Swap 3
- n= 3: 1,5
- n= 4: 1,14,9
- n= 5: 1,30,89
- n= 6: 1,55,439,225
- n= 7: 1,91,1519,3429
- n= 8: 1,140,4214,24940,11025
- n= 9: 1,204,10038,122156,230481
h3.Swap 4
- n= 4: 1,23
- n= 5: 1,75,44
- n= 6: 1,190,529
- n= 7: 1,406,4633
- n= 8: 1,770,27341,12208
- n= 9: 1,1338,118173,243368
