A164366 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).
1, 1, 1, 1, 4, 1, 1, 10, 12, 1, 1, 20, 68, 31, 1, 35, 259, 380, 45, 1, 56, 770, 2700, 1513, 1, 84, 1932, 13467, 22000, 2836, 1, 120, 4284, 52512, 191636, 114327, 1, 165, 8646, 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
Offset: 1
Examples
The triangle of T(n,k) (with rows n >= 1 and columns k >= 0) starts as follows: 1, 1, 1, 1, 4, 1, 1, 10, 12, 1, 1, 20, 68, 31, 1, 35, 259, 380, 45, 1, 56, 770, 2700, 1513, 1, 84, 1932, 13467, 22000, 2836, 1, 120, 4284, 52512, 191636, 114327, 1, 165, 8646, 170907, 1183457, 2010571, 255053, ... 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).
References
- G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009, page 26.
Links
- V. Bafna and P. A. Pevzner, Sorting by transpositions, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
- V. Bafna and P. A. Pevzner, Sorting by transpositions, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
- J. Gonçalves, L. R. Bueno, R. A. Hausen, Assembling a New and Improved Transposition Distance Database, in Simpósio Brasileiro de Pesquisa Operacional, Sept. 2013.
Extensions
Edited by Max Alekseyev, Nov 07 2011
More terms from Gonçalves et al. added by Max Alekseyev, Nov 16 2012
Comments