A115755 Number of permutations of n elements whose unsigned reversal distance is k.

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

Offset: 1

Author

Anthony Labarre, Mar 29 2006, Jun 03 2006

Keywords

• nonn
• tabl

Comments

Probably an erroneous version of A300003. Some inner terms of the triangle differ slightly. Sean A. Irvine reread the paper and checked manually that a(13) should be 52. The last row 1, 36, 820 ... 6352, 2 was added later and is ok. - Georg Fischer, Feb 24 2020

Examples

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

Links

• J. D. Kececioglu, and D. Sankoff, Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement, Algorithmica (1995) 13:180.

Crossrefs

Cf. A300003.