cp's OEIS Frontend

A235757 Ruler function associated with the set of permutations generated by cyclic shift in cyclic order, array read by rows.

%I A235757 #15 Jan 20 2014 10:58:07
%S A235757 1,1,1,1,2,1,1,2,1,1,1,2,1,1,1,2,1,1,1,3,1,1,1,2,1,1,1,2,1,1,1,3,1,1,
%T A235757 1,1,2,1,1,1,1,2,1,1,1,1,2,1,1,1,1,3,1,1,1,1,2,1,1,1,1,2,1,1,1,1,2,1,
%U A235757 1,1,1,3,1,1,1,1,2,1,1,1,1,2,1,1,1,1,2,1,1,1,1,4
%N A235757 Ruler function associated with the set of permutations generated by cyclic shift in cyclic order, array read by rows.
%C A235757 Variant of A235748.
%C A235757 The set of permutations S_n = {p_0, ..., p_{n!-1}} is ordered according to generation by cyclic shift. The order is considered cyclic, i.e., p_0 is next to p_{n!-1}.
%C A235757 Row n, denoted F(n), has n! (A000142) entries.
%C A235757 F(2) = 1 1
%C A235757 F(3) = 1 1 2 1 1 2
%C A235757 F(4) = 1 1 1 2 1 1 1 2 1 1 1 3 1 1 1 2 1 1 1 2 1 1 1 3
%C A235757 F(5) = 111121111211112111131111211112111121111311112111121111211114...4
%C A235757 The term of index k (k = 0, ..., n!-1) of row n is the number of symbols that have to be erased to the left of a permutation p_k so that the last symbols of the permutation match the first symbols of the next permutation p_{k+1}. The terms of F(n) sum to 1! + 2! + ... + n! - 1.
%D A235757 D. E. Knuth, The Art of Computer Programming, Vol. 4, Combinatorial Algorithms, 7.2.1.2, Addison-Wesley, 2005.
%H A235757 S. Legendre and P. Paclet, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Legendre/legendre5.html">On the permutations generated by cyclic shift</a>, J. Integer Seqs., Vol. 14, article 11.3.2, 2011.
%H A235757 F. Ruskey and A. Williams, <a href="http://arxiv.org/abs/0710.1842">An explicit universal cycle for the (n-1)-permutations of an n-set</a>, ACM Trans. Algorithms, Vol. 6(3), article 45, 12 pages, 2010.
%F A235757 F(n) := if n = 2 then 11 else
%F A235757 (a) Set F'(n-1)  equal to F(n-1) with all entries incremented by 1;
%F A235757 (b) Insert a run of n-1 ones between all entries of F'(n-1) and at the beginning.
%F A235757 Sequence a = F(2)F(3)...
%e A235757 S_2 = {12,21}.
%e A235757 S_3 = {123,231,312,213,132,321}, generated by cyclic shift from S_2.
%e A235757 The ruler sequence is F(6) = 1 1 2 1 1 2. For example, 2 terms need to be erased to the left of p_6 = 321 to match the first symbols of p_0 = 123.
%t A235757 a[nmax_] := Module[{n,b={},w,f,g,i,k},
%t A235757 Do[w = {};f = n!-1;Do[w = Append[w,1],{i,1,f}];
%t A235757    g = 1;
%t A235757    Do[g = g*k;
%t A235757       Do[If[Mod[i,g] == 0,w[[i]] = w[[i]]+1],{i,1,f}],
%t A235757       {k,n,2,-1}];
%t A235757    w = Append[w,n-1];
%t A235757    b = Join[b,w],
%t A235757    {n,2,nmax}];
%t A235757 b]
%t A235757 (* or: *) row[2] = {1, 1}; row[n_] := row[n] = Riffle[Table[Array[1&, n-1], {Length[row[n-1]]}], row[n-1]+1] // Flatten; row /@ Range[2, 5] // Flatten (* _Jean-François Alcover_, Jan 16 2014 *)
%K A235757 nonn,tabf
%O A235757 2,5
%A A235757 _Stéphane Legendre_, Jan 15 2014