A164645 Triangle read by rows: a(n,k) is the number of permutations of n elements with prefix transposition distance equal to k.

1, 1, 1, 1, 3, 2, 1, 6, 14, 3, 1, 10, 50, 55, 4, 1, 15, 130, 375, 194, 5, 1, 21, 280, 1575, 2598, 562, 3, 1, 28, 532, 4970, 18096, 15532, 1161, 0, 1, 36, 924, 12978, 85128, 188386, 74183, 1244, 0, 1, 45, 1500, 29610, 308988, 1364710, 1679189, 244430, 327

Offset

1,5

Comments

A prefix transposition refers to the displacement of the first f elements of the permutation. The prefix transposition distance is the minimum number of such moves required to transform a given permutation into the identity permutation.

References

Zanoni Dias and Joao Meidanis, Sorting by Prefix Transpositions, Proceedings of the Ninth International Symposium on String Processing and Information Retrieval (SPIRE), 2002, 65-76, vol. 2476 of Lecture Notes in Computer Science, Springer-Verlag

G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009, page 37.

Links

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

G. Fertin, A. Labarre, I. Rusu, E. Tannier, and S. Vialette, "Combinatorics of genome rearrangements", The MIT Press, 2009.

Example

a(4,2)=3 because the only 3 permutations that require 2 prefix transpositions to be sorted are (1 4 3 2), (2 1 4 3) and (4 3 2 1)

Crossrefs

Sequence in context: A367023 A143778 A200536 * A115755 A300003 A259879

Adjacent sequences: A164642 A164643 A164644 * A164646 A164647 A164648

Keyword

nonn,tabl

Author

Anthony Labarre, Aug 19 2009

Status

approved