|
Search: id:A164366
|
|
|
| A164366 |
|
a(n,k) is the number of permutations of n elements with transposition distance equal to k. Here, a transposition refers to the exchange of two adjacent intervals, and NOT to an exchange of two nonnecessary adjacent elements. The transposition distance is the minimum number of such moves required to transform a given permutation into the identity permutation. |
|
+0
1
|
|
| 1, 1, 1, 1, 4, 1, 1, 10, 12, 1, 1, 20, 68, 31, 0, 1, 35, 259, 380, 45, 0, 1, 56, 770, 2700, 1513, 0, 0, 1, 84, 1932, 13467, 22000, 2836, 0, 0, 1, 120, 4284, 52512, 191636, 114327, 0, 0, 0, 1, 165, 8646, 170907, 1183457, 2010571, 255053, 0, 0, 0
(list; table; graph; listen)
|
|
|
OFFSET
|
1,5
|
|
|
REFERENCES
|
G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009, page 26.
V. Bafna and P. A. Pevzner, "Sorting by transpositions", SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
|
|
LINKS
|
G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009, page 26.
|
|
EXAMPLE
|
The number of permutations of 4 elements with transposition distance 3 is 1, since only (4 3 2 1) cannot be sorted using fewer transpositions (upper bound can be easily found by hand; for the lower bound, see the paper by Bafna and Pevzner).
|
|
CROSSREFS
|
Sequence in context: A056939 A142595 A140711 this_sequence A121692 A145271 A147564
Adjacent sequences: A164363 A164364 A164365 this_sequence A164367 A164368 A164369
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Anthony Labarre (alabarre(AT)ulb.ac.be), Aug 14 2009
|
|
|
Search completed in 0.002 seconds
|
