This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A165325 Triangle |S_{n,N}| read by rows, the number of permutations of [1..n] that are realized by a shift on N symbols. 0
 2, 6, 18, 6, 48, 66, 6, 126, 402, 186, 6, 306, 2028, 2232, 468, 6, 738, 8790, 19426, 10212, 1098, 6 (list; graph; refs; listen; history; text; internal format)
 OFFSET 2,1 COMMENTS From Table 3.1., p.10, of the Elizalde arXiv preprint. A permutation p is realized by the shift on N symbols if there is an infinite word on an N-letter alphabet whose successive left shifts by one position are lexicographically in the same relative order as p. The set of realized permutations is closed under consecutive pattern containment. Permutations that cannot be realized are called forbidden patterns. It was shown in [Amigo et al.] that the shortest forbidden patterns of the shift on N symbols have length N+2. In this paper we give a characterization of the set of permutations that are realized by the shift on N symbols, and we enumerate them according to their length. LINKS Amigo, Elizalde and Kennel, Forbidden patterns and shift systems, J. Combin. Theory Ser. A 115 (2008) 485-504. Sergi Elizalde, The number of permutations realized by a shift, arXiv:0909.2274 EXAMPLE 2; 6; 18,6; 48,66,6; 126,402,186,6; 306,2028,2232,468,6; CROSSREFS Sequence in context: A253882 A183757 A181490 * A316765 A097635 A151870 Adjacent sequences:  A165322 A165323 A165324 * A165326 A165327 A165328 KEYWORD nonn,tabf AUTHOR Jonathan Vos Post, Sep 14 2009 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.

Last modified May 22 07:19 EDT 2019. Contains 323478 sequences. (Running on oeis4.)