|
|
A235757
|
|
Ruler function associated with the set of permutations generated by cyclic shift in cyclic order, array read by rows.
|
|
0
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,5
|
|
COMMENTS
|
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.
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming, Vol. 4, Combinatorial Algorithms, 7.2.1.2, Addison-Wesley, 2005.
|
|
LINKS
|
|
|
FORMULA
|
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)...
|
|
EXAMPLE
|
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.
|
|
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}];
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|