

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 Nletter 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) 485504.
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



