|
| |
|
|
A115755
|
|
Number of permutations of n elements whose unsigned reversal distance is k.
|
|
0
|
|
|
|
1, 1, 1, 1, 3, 2, 1, 6, 15, 2, 1, 10, 51, 56, 2, 1, 15, 127, 390, 185, 2, 1, 21, 263, 1562, 2543, 648, 2, 1, 28, 483, 4635, 16445, 16615, 2111, 2, 1, 36, 820, 11407, 69863, 169034, 105365, 6352, 2
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
REFERENCES
|
Kececioglu, J. and Sankoff, D.: Exact and Approximation Algorithms for Sorting by Reversals, with Application to Genome Rearrangement, Algorithmica, 13 (1-2), pp. 180-210, 1995.
|
|
|
LINKS
|
Table of n, a(n) for n=1..45.
|
|
|
EXAMPLE
|
a(3,1) = 3 because the only three permutations of S_3 that require exactly one reversal to be sorted are (1 3 2), (2 1 3) and (3 2 1).
|
|
|
CROSSREFS
|
Sequence in context: A143778 A200536 A164645 * A016556 A067050 A001355
Adjacent sequences: A115752 A115753 A115754 * A115756 A115757 A115758
|
|
|
KEYWORD
|
more,nonn,tabl
|
|
|
AUTHOR
|
Anthony Labarre, Mar 29 2006, Jun 03 2006
|
|
|
STATUS
|
approved
|
| |
|
|
