login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

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