login
Triangle read by rows: T(n,k) is the number of permutations of n elements with transposition distance equal to k, n >= 1 and 0 <= k <= A065603(n).
2

%I #28 Dec 17 2019 07:42:22

%S 1,1,1,1,4,1,1,10,12,1,1,20,68,31,1,35,259,380,45,1,56,770,2700,1513,

%T 1,84,1932,13467,22000,2836,1,120,4284,52512,191636,114327,1,165,8646,

%U 170907,1183457,2010571,255053,1,220,16203,484440,5706464,21171518,12537954,1,286,28600,1231230,22822293,157499810,265819779,31599601,1,364,48048,2864719,78829491,910047453,3341572727,1893657570,427,1,455,77441,6196333,241943403,4334283646,29432517384,47916472532,5246800005

%N Triangle read by rows: T(n,k) is the number of permutations of n elements with transposition distance equal to k, n >= 1 and 0 <= k <= A065603(n).

%C Here, a transposition refers to the exchange of two adjacent blocks, and NOT to an exchange of two nonnecessarily adjacent elements. The transposition distance is the minimum number of such moves required to transform a given permutation into the identity permutation.

%D G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009, page 26.

%H V. Bafna and P. A. Pevzner, <a href="https://doi.org/10.1137/S089548019528280X">Sorting by transpositions</a>, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.

%H V. Bafna and P. A. Pevzner, <a href="http://www.ic.unicamp.br/~meidanis/courses/mo640/2007s1/textos/Bafna-Pevzner-1998.pdf">Sorting by transpositions</a>, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.

%H J. Gonçalves, L. R. Bueno, R. A. Hausen, <a href="https://pdfs.semanticscholar.org/b9df/0c38ed7fca7d5046513de19895412c9ff2c0.pdf">Assembling a New and Improved Transposition Distance Database</a>, in Simpósio Brasileiro de Pesquisa Operacional, Sept. 2013.

%e The triangle of T(n,k) (with rows n >= 1 and columns k >= 0) starts as follows:

%e 1,

%e 1, 1,

%e 1, 4, 1,

%e 1, 10, 12, 1,

%e 1, 20, 68, 31,

%e 1, 35, 259, 380, 45,

%e 1, 56, 770, 2700, 1513,

%e 1, 84, 1932, 13467, 22000, 2836,

%e 1, 120, 4284, 52512, 191636, 114327,

%e 1, 165, 8646, 170907, 1183457, 2010571, 255053,

%e ...

%e The number of permutations of 4 elements with transposition distance 3 is 1, since only (4 3 2 1) cannot be sorted using fewer transpositions (upper bound can be easily found by hand; for the lower bound, see the paper by Bafna and Pevzner).

%Y Cf. A219243 (main "diagonal"). See also A065603.

%K nonn,tabf

%O 1,5

%A _Anthony Labarre_, Aug 14 2009

%E Edited by _Max Alekseyev_, Nov 07 2011

%E More terms from Gonçalves et al. added by _Max Alekseyev_, Nov 16 2012