The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #7 Mar 31 2012 10:29:58
%S 0,0,6,66,402,2028,8790,35118,131982,475344,1658382,5651226,18912498,
%T 62418180,203768862,659487678,2119617474,6774043254,21547968726,
%U 68274910026,215609878962,678936947940,2132568719358,6683705385078,20906259913566,65277851607840
%N Number of permutations of [n] that require a 3-letter alphabet in order to be realized by a shift.
%C These permutations are those realized by the shift on 3 letters (A192088)
%C but not by the shift on 2 letters (A059413).
%D S. Elizalde, The number of permutations realized by a shift, SIAM J. Discrete Math. 23 (2009), 765--786.
%H Sergi Elizalde, <a href="http://arxiv.org/abs/0909.2274">The number of permutations realized by a shift</a>, arXiv:0909.2274v1 [math.CO]
%F a(n)=3^(n-2)+sum(psi_3(t)*3^(n-t-1),t=1..n-1)-n*sum(psi_2(t)*2^(n-t-1),t=0..n-1), where psi_N(t) is the number of primitive words of length t over an N-letter alphabet, which is expressible in terms of the Möbius function.
%e a(4)=6 because the permutations 1423, 3241, 4132, 2314 3421, 2134 are the only ones of length 4 that require 3 letters in order to be realized by a shift
%Y Equals A192088 minus A059413
%K nonn
%O 2,3
%A _Sergi Elizalde_, Jun 23 2011