|
Search: id:A164645
|
|
|
| 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, 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; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
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: A008276 A094638 A143778 this_sequence A115755 A016556 A067050
Adjacent sequences: A164642 A164643 A164644 this_sequence A164646 A164647 A164648
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Anthony Labarre (alabarre(AT)ulb.ac.be), Aug 19 2009
|
|
|
Search completed in 0.002 seconds
|
