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,1

References

S. Elizalde, The number of permutations realized by a shift, SIAM J. Discrete Math. 23 (2009), 765--786.

Links

Table of n, a(n) for n=2..27.

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

Cf. A059413.

Sequence in context: A152325 A152329 A216716 * A245233 A228907 A209625

Adjacent sequences: A192085 A192086 A192087 * A192089 A192090 A192091

Keyword

nonn

Author

Sergi Elizalde, Jun 23 2011

Status

approved