A207324 List of permutations of 1,2,3,...,n for n=1,2,3,..., in the order they are output by Steinhaus-Johnson-Trotter algorithm.

1, 1, 2, 2, 1, 1, 2, 3, 1, 3, 2, 3, 1, 2, 3, 2, 1, 2, 3, 1, 2, 1, 3, 1, 2, 3, 4, 1, 2, 4, 3, 1, 4, 2, 3, 4, 1, 2, 3, 4, 1, 3, 2, 1, 4, 3, 2, 1, 3, 4, 2, 1, 3, 2, 4, 3, 1, 2, 4, 3, 1, 4, 2, 3, 4, 1, 2, 4, 3, 1, 2, 4, 3, 2, 1, 3, 4, 2, 1, 3, 2, 4, 1, 3, 2, 1, 4

Offset: 1

Author

R. J. Cano, Sep 14 2012

Keywords

• nonn
• easy
• tabf

Comments

This table is otherwise similar to A030298, but lists permutations in the order given by the Steinhaus-Trotter-Johnson algorithm. - Antti Karttunen, Dec 28 2012

Examples

			For the set of the first two natural numbers {1,2} the unique permutations possible are 12 and 21, concatenated with 1 for {1} the resulting sequence would be 1, 1, 2, 2, 1.
If we consider up to 3 elements {1,2,3}, we have 123, 132, 312, 321, 231, 213 and the concatenation gives: 1, 1, 2, 2, 1, 1, 2, 3, 1, 3, 2, 3, 1, 2, 3, 2, 1, 2, 3, 1, 2, 1, 3.
Up to N concatenations, the sequence will have a total of Sum_{k=1..N} (k! * k) = (N+1)! - 1 = A033312(N+1) terms.
		

Links

• R. J. Cano, Table of n, a(n) for n = 1..10000
• Joerg Arndt, C programs related to this sequence
• R. J. Cano, Sequencer programs and additional information
• Selmer M. Johnson, Generation of permutations by adjacent transposition, Mathematics of Computation, 17 (1963), p. 282-285.
• Wikipedia, Steinhaus-Johnson-Trotter algorithm
• Index entries for sequences related to permutations

Crossrefs

Cf. A030298, A055881.

Cf. A001563 (row lengths), A001286 (row sums).

Pair (A130664(n),A084555(n)) = (1,1),(2,3),(4,5),(6,8),(9,11),(12,14),... gives the starting and ending offsets of the n-th permutation in this list.

Extensions

Edited by N. J. A. Sloane, Antti Karttunen and R. J. Cano