|
%I #125 Dec 05 2018 00:32:54
%S 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,
%T 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,
%U 3,1,2,4,3,2,1,3,4,2,1,3,2,4,1,3,2,1,4
%N List of permutations of 1,2,3,...,n for n=1,2,3,..., in the order they are output by Steinhaus-Johnson-Trotter algorithm.
%C 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
%H R. J. Cano, <a href="/A207324/b207324.txt">Table of n, a(n) for n = 1..10000</a>
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/demo/comb/#perm-trotter">C programs related to this sequence</a>
%H R. J. Cano, <a href="/wiki/User:R._J._Cano/Permutation_Sequences"> Sequencer programs and additional information</a>
%H Selmer M. Johnson, <a href="https://doi.org/10.1090/S0025-5718-1963-0159764-2">Generation of permutations by adjacent transposition</a>, Mathematics of Computation, 17 (1963), p. 282-285.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm">Steinhaus-Johnson-Trotter algorithm</a>
%H <a href="/index/Per#perm">Index entries for sequences related to permutations</a>
%e 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.
%e 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.
%e Up to N concatenations, the sequence will have a total of Sum_{k=1..N} (k! * k) = (N+1)! - 1 = A033312(N+1) terms.
%Y Cf. A030298, A055881.
%Y Cf. A001563 (row lengths), A001286 (row sums).
%Y 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.
%K nonn,easy,tabf
%O 1,3
%A _R. J. Cano_, Sep 14 2012
%E Edited by _N. J. A. Sloane_, _Antti Karttunen_ and _R. J. Cano_
|
