login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A192089 Number of permutations of [n] that require a 3-letter alphabet in order to be realized by a shift. 0
0, 0, 6, 66, 402, 2028, 8790, 35118, 131982, 475344, 1658382, 5651226, 18912498, 62418180, 203768862, 659487678, 2119617474, 6774043254, 21547968726, 68274910026, 215609878962, 678936947940, 2132568719358, 6683705385078, 20906259913566, 65277851607840 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,3

COMMENTS

These permutations are those realized by the shift on 3 letters (A192088)

but not by the shift on 2 letters (A059413).

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*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.

EXAMPLE

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

CROSSREFS

Equals A192088 minus A059413

Sequence in context: A064167 A175455 A185253 * A119073 A028559 A249639

Adjacent sequences:  A192086 A192087 A192088 * A192090 A192091 A192092

KEYWORD

nonn

AUTHOR

Sergi Elizalde, Jun 23 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 22 10:56 EDT 2021. Contains 345375 sequences. (Running on oeis4.)