cp's OEIS Frontend

A059413 Number of distinct languages accepted by unary DFA's with n states.

%I A059413 #30 Apr 26 2022 21:11:25
%S A059413 2,6,18,48,126,306,738,1716,3936,8862,19770,43560,95310,206874,446478,
%T A059413 958236,2047542,4356660,9237606,19522752,41142522,86477298,181343202,
%U A059413 379459284,792472968,1652046606,3438310428,7145039916,14826950742
%N A059413 Number of distinct languages accepted by unary DFA's with n states.
%C A059413 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]
%C A059413 Also, sum over A059412(1..n), hence number of ultimately periodic binary sequences uvvvv... with |u|+|v| <= n. - _Michael Vielhaber_, Mar 19 2022
%D A059413 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)
%D A059413 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
%D A059413 Jeffrey Shallit, Notes on Enumeration of Finite Automata, manuscript, Jan 30, 2001
%H A059413 Sergi Elizalde, <a href="http://arxiv.org/abs/0909.2274">The number of permutations realized by a shift</a>, SIAM J. Discrete Math. 23 (2009), pp. 765-786; arXiv:0909.2274 [math.CO], 2009.
%F A059413 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).
%F A059413 Hence, a(n) = 2*a(n-1) + psi(n), with a(0)=0 or a(1)=2.
%e A059413 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.
%p A059413 A059413 := proc(n)
%p A059413     add(A027375(t)*2^(n-t),t=1..n) ;
%p A059413 end proc:
%p A059413 seq(A059413(n),n=1..10) ; # _R. J. Mathar_, May 21 2018
%t A059413 a[n_] := Sum[DivisorSum[k, MoebiusMu[k/#]*2^#&]*2^(n-k), {k, 1, n}];
%t A059413 Array[a, 30] (* _Jean-François Alcover_, Jul 10 2018 *)
%K A059413 nonn
%O A059413 1,1
%A A059413 _Jeffrey Shallit_, Jan 30 2001