OFFSET
1,1
COMMENTS
Start with (1,2,3,4), i.e. the first permutation of {1,2,3} followed by 4; then for each next permutation, transpose 4 one to the left; if at position 1, replace {1,2,3} recursively by the next permutation of these numbers. Thereafter, for each next permutation, transpose 4 to the right. And so on.
LINKS
Richard Duckworth and Fabian Stedman, Tintinnalogia, or, the Art of Ringing, (1671). Released by Project Gutenberg, 2006.
Wikipedia, Steinhaus-Johnson-Trotter Algorithm
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,0,0,0,-1,1).
FORMULA
Period 24.
From Chai Wah Wu, Jan 15 2020: (Start)
a(n) = a(n-1) - a(n-12) + a(n-13) for n > 13.
G.f.: x*(-x^12 - x^9 + x^7 - x^4 - x^2 - 2)/(x^13 - x^12 + x - 1). (End)
MAPLE
ring:= proc(k::nonnegint) local p, i, left, l, nf, ini; if k<=1 then proc() [1$k] end else ini := proc() p:= ring(k-1); i:= k; left:= true; l:= p(); nf:= k! end; ini(); proc() local ll; ll:= [seq(l[t], t=1..(i-1)), k, seq(l[t], t=i..(k-1))]; if left then if i>1 then i:= i-1 else left:= false; l:=p() fi else if i<k then i:= i+1 else left:= true; l:=p() fi fi; nf:= nf-1; if nf = 0 then ini() fi; ll end fi end: bell := proc(k) option remember; local p; p:= ring(k); [seq(p(), i=1..k!)] end: indx:= proc(l, k) local i; for i from 1 to nops(l) do if l[i]=k then break fi od; i end: a := n-> indx (bell(4)[modp(n-1, 24)+1], 2): seq (a(n), n=1..121);
MATHEMATICA
LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1}, {2, 2, 3, 3, 4, 4, 4, 3, 3, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 2, 2}, 105] (* Jean-François Alcover, Mar 15 2021 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Aug 19 2008
STATUS
approved