|
%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
|
