login
A235748
Ruler function associated with the set of permutations generated by cyclic shift, array read by rows.
2
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, 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,4
COMMENTS
The sequence is to permutations what the ruler function (A001511) is to binary numbers.
Row n is the ruler sequence E(n) associated with the set of permutations S_n, n >= 2.
E(n) has n!-1 (A033312) entries.
E(2) = 1
E(3) = 1 1 2 1 1
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
E(5) = 111121111211112111131111211112111121111311112111121111211114...
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}.
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.
REFERENCES
D. E. Knuth, The Art of Computer Programming, Vol. 4, Combinatorial Algorithms, 7.2.1.2, Addison-Wesley, 2005.
LINKS
Stéphane Legendre, Illustration of initial terms
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.
FORMULA
E(n) := if n = 2 then 1 else
(a) Set E'(n-1) equal to E(n-1) with all entries incremented by 1;
(b) Insert a run of n-1 ones between all entries of E'(n-1) and at both extremities.
Sequence a = E(2)E(3)...
EXAMPLE
S_2 = {12,21}.
S_3 = {123,231,312,213,132,321}, generated by cyclic shift from S_2.
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.
MATHEMATICA
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}];
b = Join[b, w], {n, 2, nmax}];
b]
(* 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 *)
CROSSREFS
Sequence in context: A282749 A132587 A318930 * A204697 A208576 A307897
KEYWORD
nonn,tabf
AUTHOR
Stéphane Legendre, Jan 15 2014
STATUS
approved