|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Gonçalves et al. added by Max Alekseyev, Nov 16 2012
|
|
STATUS
|
approved
|
|
|
|