The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A059413 Number of distinct languages accepted by unary DFA's with n states. 4
 2, 6, 18, 48, 126, 306, 738, 1716, 3936, 8862, 19770, 43560, 95310, 206874, 446478, 958236, 2047542, 4356660, 9237606, 19522752, 41142522, 86477298, 181343202, 379459284, 792472968, 1652046606, 3438310428, 7145039916, 14826950742 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,1 COMMENTS a(n) is also the number of permutations of [n+1] realized by the binary shift. The binary shift is the operation (w_1,w_2,w_3,...) -> (w_2,w_3,...) on infinite binary words. The relative order (lexicographically) of the first k shifts of a word, assuming they are all different, determines a realized permutation of length k. [Sergi Elizalde, Jun 23 2011] Also, sum over A059412(1..n), hence number of ultimately periodic binary sequences uvvvv... with |u|+|v| <= n. - Michael Vielhaber, Mar 19 2022 REFERENCES M. Domaratzki, D. Kisman, and J. Shallit, On the number of distinct languages accepted by finite automata with n states, J. Autom. Lang. Combinat. 7 (2002) 4-18, Section 6, g_1(n) Cyril Nicaud, Average state complexity of operations on unary automata, Math. Foundations of Computer Science, 1999, Lect. Notes in Computer Sci. #1672, pp. 231-240 Jeffrey Shallit, Notes on Enumeration of Finite Automata, manuscript, Jan 30, 2001 LINKS Sergi Elizalde, The number of permutations realized by a shift, SIAM J. Discrete Math. 23 (2009), pp. 765-786; arXiv:0909.2274 [math.CO], 2009. FORMULA sum(psi(t)*2^(n-t), t=1..n), where psi(n) is number of primitive words of length n over a 2-letter alphabet (expressible in terms of the Moebius function). Hence, a(n) = 2*a(n-1) + psi(n), with a(0)=0 or a(1)=2. EXAMPLE a(1) = 2 because there are exactly two languages accepted by unary DFA's with 1 state. Also, because both permutations of length 2 are realized by the binary shift: the word 01000... realizes 12, and the word 1000... realizes 21. MAPLE A059413 := proc(n) add(A027375(t)*2^(n-t), t=1..n) ; end proc: seq(A059413(n), n=1..10) ; # R. J. Mathar, May 21 2018 MATHEMATICA a[n_] := Sum[DivisorSum[k, MoebiusMu[k/#]*2^#&]*2^(n-k), {k, 1, n}]; Array[a, 30] (* Jean-François Alcover, Jul 10 2018 *) CROSSREFS Sequence in context: A018027 A218759 A295499 * A256828 A197055 A258625 Adjacent sequences: A059410 A059411 A059412 * A059414 A059415 A059416 KEYWORD nonn AUTHOR Jeffrey Shallit, Jan 30 2001 STATUS approved

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

Last modified January 30 16:55 EST 2023. Contains 359945 sequences. (Running on oeis4.)