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

%I #6 Mar 30 2012 18:40:50

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

%T 10212,1098,6

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

%C 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.

%H Amigo, Elizalde and Kennel, <a href="http://dx.doi.org/10.1016/j.jcta.2007.07.004">Forbidden patterns and shift systems</a>, J. Combin. Theory Ser. A 115 (2008) 485-504.

%H Sergi Elizalde, <a href="http://arxiv.org/abs/0909.2274">The number of permutations realized by a shift</a>, arXiv:0909.2274

%e 2;

%e 6;

%e 18,6;

%e 48,66,6;

%e 126,402,186,6;

%e 306,2028,2232,468,6;

%K nonn,tabf

%O 2,1

%A _Jonathan Vos Post_, Sep 14 2009