|
| |
|
|
A164366
|
|
a(n,k) is the number of permutations of n elements with transposition distance equal to k, 0 <= k <= A065603(n).
|
|
1
| |
|
|
1, 1, 1, 1, 4, 1, 1, 10, 12, 1, 1, 20, 68, 31, 1, 35, 259, 380, 45, 1, 56, 770, 2700, 1513, 1, 84, 1932, 13467, 22000, 2836, 1, 120, 4284, 52512, 191636, 114327, 1, 165, 8646, 170907, 1183457, 2010571, 255053
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,5
|
|
|
COMMENTS
| Here, a transposition refers to the exchange of two adjacent blocks, 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.
|
|
|
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 triangle of a(n,k) start with:
1,
1, 1,
1, 4, 1,
1, 10, 12, 1,
1, 20, 68, 31,
1, 35, 259, 380, 45,
1, 56, 770, 2700, 1513,
1, 84, 1932, 13467, 22000, 2836,
1, 120, 4284, 52512, 191636, 114327,
1, 165, 8646, 170907, 1183457, 2010571, 255053,
...
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: A142595 A174669 A140711 * A121692 A145271 A203860
Adjacent sequences: A164363 A164364 A164365 * A164367 A164368 A164369
|
|
|
KEYWORD
| nonn,tabf,more
|
|
|
AUTHOR
| Anthony Labarre (alabarre(AT)ulb.ac.be), Aug 14 2009
|
|
|
EXTENSIONS
| Edited by Max Alekseyev (maxale(AT)gmail.com), Nov 07 2011
|
| |
|
|
