login
Triangle read by rows: a(n,k) is the number of permutations of n elements with prefix transposition distance equal to k.
0

%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&amp;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