|
| |
|
|
A164645
|
|
Triangle read by rows: a(n,k) is the number of permutations of n elements with prefix transposition distance equal to k.
|
|
0
| |
|
|
1, 1, 1, 1, 3, 2, 1, 6, 14, 3, 1, 10, 50, 55, 4, 1, 15, 130, 375, 194, 5, 1, 21, 280, 1575, 2598, 562, 3, 1, 28, 532, 4970, 18096, 15532, 1161, 0, 1, 36, 924, 12978, 85128, 188386, 74183, 1244, 0, 1, 45, 1500, 29610, 308988, 1364710, 1679189, 244430, 327
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,5
|
|
|
COMMENTS
| A prefix transposition refers to the displacement of the first f elements of the permutation. The prefix transposition distance is the minimum number of such moves required to transform a given permutation into the identity permutation.
|
|
|
REFERENCES
| Zanoni Dias and Joao Meidanis, Sorting by Prefix Transpositions, Proceedings of the Ninth International Symposium on String Processing and Information Retrieval (SPIRE), 2002, 65-76, vol. 2476 of Lecture Notes in Computer Science, Springer-Verlag
G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009, page 37.
|
|
|
LINKS
| G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009.
|
|
|
EXAMPLE
| a(4,2)=3 because the only 3 permutations that require 2 prefix transpositions to be sorted are (1 4 3 2), (2 1 4 3) and (4 3 2 1)
|
|
|
CROSSREFS
| Sequence in context: A196843 A143778 A200536 * A115755 A016556 A067050
Adjacent sequences: A164642 A164643 A164644 * A164646 A164647 A164648
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Anthony Labarre (alabarre(AT)ulb.ac.be), Aug 19 2009
|
| |
|
|
