login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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.

REFERENCES

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

LINKS

Table of n, a(n) for n=2..93.

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

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

Sequence in context: A173264 A056731 A042974 * A020906 A220280 A191774

Adjacent sequences:  A235754 A235755 A235756 * A235758 A235759 A235760

KEYWORD

nonn,tabf

AUTHOR

Stéphane Legendre, Jan 15 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 15:24 EST 2021. Contains 349581 sequences. (Running on oeis4.)