login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 2
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 (list; graph; refs; listen; history; text; internal format)
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
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
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)