|
|
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;
text;
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
|
|
|
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|