OFFSET
2,1
REFERENCES
S. Elizalde, The number of permutations realized by a shift, SIAM J. Discrete Math. 23 (2009), 765--786.
LINKS
Sergi Elizalde, The number of permutations realized by a shift, arXiv:0909.2274v1 [math.CO]
FORMULA
a(n)=3^(n-2)+sum(psi_3(t)*3^(n-t-1),t=1..n-1)-(n-1)*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, expressible in terms of the Möbius function.
CROSSREFS
KEYWORD
nonn
AUTHOR
Sergi Elizalde, Jun 23 2011
STATUS
approved