Swap distances between permutations

Apr 19, 02:36 PM

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

Swap 5
  • n= 5: 1,119
  • n= 6: 1,454,265
  • n= 7: 1,1330,3709
  • n= 8: 1,3234,37085
  • n= 9: 1,6882,355997

---

Comment

Commenting is closed for this article.

---