Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #3 Mar 31 2012 20:17:54
%S 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,
%T 2598,562,3,1,28,532,4970,18096,15532,1161,0,1,36,924,12978,85128,
%U 188386,74183,1244,0,1,45,1500,29610,308988,1364710,1679189,244430,327
%N Triangle read by rows: a(n,k) is the number of permutations of n elements with prefix transposition distance equal to k.
%C 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.
%D 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
%D G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009, page 37.
%H G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, <a href="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=11899">"Combinatorics of genome rearrangements"</a>, The MIT Press, 2009.
%e 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)
%K nonn,tabl
%O 1,5
%A _Anthony Labarre_, Aug 19 2009