A165325 Triangle |S_{n,N}| read by rows, the number of permutations of [1..n] that are realized by a shift on N symbols.

2, 6, 18, 6, 48, 66, 6, 126, 402, 186, 6, 306, 2028, 2232, 468, 6, 738, 8790, 19426, 10212, 1098, 6

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: A356011 A181490 A340210 * A316765 A097635 A151870

Adjacent sequences: A165322 A165323 A165324 * A165326 A165327 A165328

Keyword

nonn,tabf

Author

Jonathan Vos Post, Sep 14 2009

Status

approved