cp's OEIS Frontend

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

%I A235748 #14 Jan 16 2014 10:14:07
%S A235748 1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,3,1,1,1,2,1,1,1,2,1,1,1,1,1,1,1,2,
%T A235748 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,
%U A235748 3,1,1,1,1,2,1,1,1,1,2,1,1,1,1,2,1,1,1,1,4
%N A235748 Ruler function associated with the set of permutations generated by cyclic shift, array read by rows.
%C A235748 The sequence is to permutations what the ruler function (A001511) is to binary numbers.
%C A235748 Row n is the ruler sequence E(n) associated with the set of permutations S_n, n >= 2.
%C A235748 E(n) has n!-1 (A033312) entries.
%C A235748 E(2) = 1
%C A235748 E(3) = 1 1 2 1 1
%C A235748 E(4) = 1 1 1 2 1 1 1 2 1 1 1 3 1 1 1 2 1 1 1 2 1 1 1
%C A235748 E(5) = 111121111211112111131111211112111121111311112111121111211114...
%C A235748 When S_n = {p_0, ..., p_{n!-1}} is ordered according to generation by cyclic shift, the term of index k (k = 0, ..., n!-2) 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}.
%C A235748 E(n) is a palindrome, its terms sum to 1! + 2! + ... + n! - n, and any integer 1 <= i <= n-1 appears (n - i)(n - i)! times.
%D A235748 D. E. Knuth, The Art of Computer Programming, Vol. 4, Combinatorial Algorithms, 7.2.1.2, Addison-Wesley, 2005.
%H A235748 Stéphane Legendre, <a href="/A235748/a235748_2.pdf">Illustration of initial terms</a>
%H A235748 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 A235748 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 A235748 E(n) := if n = 2 then 1 else
%F A235748 (a) Set E'(n-1)  equal to E(n-1) with all entries incremented by 1;
%F A235748 (b) Insert a run of n-1 ones between all entries of E'(n-1) and at both extremities.
%F A235748 Sequence a = E(2)E(3)...
%e A235748 S_2 = {12,21}.
%e A235748 S_3 = {123,231,312,213,132,321}, generated by cyclic shift from S_2.
%e A235748 The ruler sequence is E(3) = 1 1 2 1 1. For example, 2 terms need to be erased to the left of p_2 = 312 to match the first symbols of p_3 = 213.
%t A235748 a[nmax_] :=
%t A235748 Module[{n, b = {}, w, f, g, i, k},
%t A235748   Do[w = {}; f = n! - 1; Do[w = Append[w, 1], {i, 1, f}];
%t A235748    g = 1;
%t A235748    Do[g = g*k;
%t A235748     Do[If[Mod[i, g] == 0, w[[i]] = w[[i]] + 1], {i, 1, f}], {k, n,
%t A235748      2, -1}];
%t A235748    b = Join[b, w], {n, 2, nmax}];
%t A235748   b]
%t A235748 (* A non-procedural variant: *) row[2] = {1}; row[n_] := row[n] = Riffle[Table[Array[1&, n-1], {Length[row[n-1]]+1}], row[n-1]+1] // Flatten; row /@ Range[2, 5] // Flatten (* _Jean-François Alcover_, Jan 16 2014 *)
%K A235748 nonn,tabf
%O A235748 2,4
%A A235748 _Stéphane Legendre_, Jan 15 2014