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,5

Comments

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.

References

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

Links

Table of n, a(n) for n=1..76.

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.

Example

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).

Crossrefs

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

Sequence in context: A142595 A174669 A140711 * A121692 A264614 A261762

Adjacent sequences: A164363 A164364 A164365 * A164367 A164368 A164369

Keyword

nonn,tabf

Author

Anthony Labarre, Aug 14 2009

Extensions

Edited by Max Alekseyev, Nov 07 2011

More terms from Gonçalves et al. added by Max Alekseyev, Nov 16 2012

Status

approved