A192088 Number of permutations of [n] realized by the shift on 3 letters.

2, 6, 24, 114, 528, 2334, 9528, 36834, 135918, 484206, 1678152, 5694786, 19007808, 62625054, 204215340, 660445914, 2121665016, 6778399914, 21557206332, 68294432778, 215651021484, 679023425238, 2132750062560, 6684084844362, 20907052386534, 65279503654446

Offset: 2

Author

Sergi Elizalde, Jun 23 2011

Keywords

• nonn

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]

Crossrefs

Cf. A059413.

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.