A235748 -id:A235748 - cp's OEIS frontend

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

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, 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, 1, 1, 1, 3, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 4

Offset: 2

Stéphane Legendre, Jan 15 2014

Variant of A235748.
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}.
Row n, denoted F(n), has n! (A000142) entries.
F(2) = 1 1
F(3) = 1 1 2 1 1 2
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
F(5) = 111121111211112111131111211112111121111311112111121111211114...4
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.

			S_2 = {12,21}.
S_3 = {123,231,312,213,132,321}, generated by cyclic shift from S_2.
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.

D. E. Knuth, The Art of Computer Programming, Vol. 4, Combinatorial Algorithms, 7.2.1.2, Addison-Wesley, 2005.

S. Legendre and P. Paclet, On the permutations generated by cyclic shift, J. Integer Seqs., Vol. 14, article 11.3.2, 2011.
F. Ruskey and A. Williams, An explicit universal cycle for the (n-1)-permutations of an n-set, ACM Trans. Algorithms, Vol. 6(3), article 45, 12 pages, 2010.

a[nmax_] := Module[{n,b={},w,f,g,i,k},
Do[w = {};f = n!-1;Do[w = Append[w,1],{i,1,f}];
   g = 1;
   Do[g = g*k;
      Do[If[Mod[i,g] == 0,w[[i]] = w[[i]]+1],{i,1,f}],
      {k,n,2,-1}];
   w = Append[w,n-1];
   b = Join[b,w],
   {n,2,nmax}];
b]
(* 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 *)

F(n) := if n = 2 then 11 else
(a) Set F'(n-1)  equal to F(n-1) with all entries incremented by 1;
(b) Insert a run of n-1 ones between all entries of F'(n-1) and at the beginning.
Sequence a = F(2)F(3)...

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Mathematica

Formula