A065603 -id:A065603

Search: a065603 -id:a065603

Displaying 1-2 of 2 results found.

page 1

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

+20
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

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.

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

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

A219243

Number of permutations of order n at the largest transposition distance (= A065603(n)) from the identity permutation.

+20
2

1, 1, 1, 1, 31, 45, 1513, 2836, 114327, 255053, 12537954, 31599601, 427, 5246800005

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

REFERENCES

J. Gonçalves, L. R. Bueno, and R. A. Hausen, "A New and Improved Transposition Distance Database", Poster at RECOMB-CG 2012.

LINKS

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

J. Gonçalves, L. R. Bueno, and R. A. Hausen, Assembling a New and Improved Transposition Distance Database, in Simpósio Brasileiro de Pesquisa Operacional, Sept. 2013.

FORMULA

a(n) = A164366(n, A065603(n)).

CROSSREFS

Cf. A065603, A164366.

KEYWORD

nonn,hard,more

AUTHOR

Max Alekseyev, Nov 16 2012

STATUS

approved

page 1

Search completed in 0.006 seconds