A059412 -id:A059412 - cp's OEIS frontend

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

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

Offset: 1

Jeffrey Shallit, Jan 30 2001

nonn

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

			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.

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

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.

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

a[n_] := Sum[DivisorSum[k, MoebiusMu[k/#]*2^#&]*2^(n-k), {k, 1, n}];
Array[a, 30] (* Jean-François Alcover, Jul 10 2018 *)

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.

A284462 Number of length-n binary strings s whose longest repeated suffix appears exactly twice in s.

Original entry on oeis.org

2, 2, 6, 10, 22, 44, 92, 178, 362, 724, 1444, 2888, 5792, 11616, 23300, 46670, 93434, 186988, 374012, 747976, 1495656, 2990440, 5979368, 11956444, 23910164, 47819272, 95645168, 191318496, 382719072, 765644448, 1531761528, 3064550802, 6131253398, 12266876820

Offset: 1

Jeffrey Shallit, Mar 27 2017

nonn

By "longest repeated suffix" we mean the longest suffix that occurs in at least one other position in the string; occurrences may overlap. Thus the longest repeated suffix of "alfalfa" is "alfa".

			For n = 4 the exceptions are 0001 and 1110 (longest repeated suffix is empty); 0010 and 0100 (longest repeated suffix is 0, which appears three times); and 1011 and 1101 (longest repeated suffix is 1, which appears three times).

Michael S. Branicky, Table of n, a(n) for n = 1..37
Michael S. Branicky, Python program

Cf. A059412, A284125.

g:= proc(S) local m,n,t;
  n:= nops(S);
for m from n-1 to 1 by -1 do
  t:= nops(select(j -> S[1..m] = S[j..m+j-1], [$2..n-m+1]));
  if t >= 1 then return evalb(t=1) fi;
od;
false
end proc:
f:= proc(n) add(`if`(g(convert(x,base,2)),2,0), x=2^(n-1)..2^n-1) end proc:
f(1):= 2:
map(f, [$1..20]); # Robert Israel, Mar 27 2017

# see link for faster version
from itertools import product
def ok(s):
    for i in range(len(s)-1, 0, -1):
        count = 1 + sum(s[j:].startswith(s[-i:]) for j in range(len(s)-i))
        if count > 1: return count == 2
    return False
def a(n):
    if n == 1: return 2
    return 2*sum(ok("1"+"".join(p)) for p in product("01", repeat=n-1))
print([a(n) for n in range(1, 17)]) # Michael S. Branicky, Aug 19 2021

a(21)-a(32) from Lars Blomberg, Jun 06 2017

a(33) and beyond from Michael S. Branicky, Aug 19 2021

A370489 Deterministic complexity of binary strings, in shortlex order.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 1, 3, 2, 2, 2, 2, 3, 1, 1, 4, 3, 3, 3, 2, 3, 2, 2, 3, 2, 3, 3, 3, 4, 1, 1, 5, 4, 4, 3, 3, 4, 3, 3, 3, 2, 4, 4, 3, 4, 2, 2, 4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 3, 4, 4, 5, 1, 1, 6, 5, 5, 4, 4, 5, 4, 4, 3, 3, 5, 4, 4, 5, 3, 3, 4, 3, 5, 5, 2

Offset: 1

Lucas B. Vieira, Mar 02 2024

a(n) = DC(w[n]), where w[n] is the n-th binary string in shortlex order: 0, 1, 00, 01, 10, 11, 000, 001, .... (row n-1 of A076478).
The Deterministic Complexity (DC) of a string w is the minimum number of states in a deterministic Mealy automaton outputting the string w. Alternatively, DC(w) = |u|+|v| for the smallest (possibly empty) u and primitive word v, such that w = trunc(uv^k,|w|) for some k >= 1, where trunc(x,L) truncates the word x to length L.
1..L each appear at least twice in row L since DC(0^i 1^(L-i)) = DC(1^i 0^(L-i)) = i+1 for i = 0..L-1. - Michael S. Branicky, Mar 03 2024

			For n = 1, w[1] = 0, and DC(w[1]) = 1. The minimal deterministic Mealy automaton outputting w[1] has a single state, transitioning to itself and outputting 0.
For n = 36, w[36] = 00101, and DC(w[36]) = 3. The minimal deterministic Mealy automaton has 3 states: transitions 1->2 and 2->3 output 0, and 3->2 outputs 1.

Michael S. Branicky, Table of n, a(n) for n = 1..10000
Lucas B. Vieira and Costantino Budroni, Temporal correlations in the simplest measurement sequences, Quantum 6 p. 623 (2022).

Cf. A059412, A076478, A370821.

(* e.g. DC[{0,0,1,0,1}] = 3 *)
DC[seq_] := With[{L = Length[seq]}, Do[If[With[{c = dc - t}, Take[Flatten[{Take[seq, t], ConstantArray[Take[Drop[seq, t], c], Ceiling[(L - t)/c]]}], L]] == seq, Return[dc]], {dc, 0, L}, {t, 0, dc - 1}]];
a[n_] := DC[Rest[IntegerDigits[n + 1, 2]]];
(* Table for all sequences up to length 10 *)
With[{L = 10}, Table[a[n], {n, 2*(2^L-1)}]]

def DC(w): return next(dc for dc in range(1, len(w)+1) for i in range(dc) if w == (w[:i]+w[i:dc]*(1+(len(w)-i)//(dc-i)))[:len(w)])
def a(n): return DC(bin(n+1)[3:])
print([a(n) for n in range(1, 88)]) # Michael S. Branicky, Mar 03 2024

A370821 Number of minimal deterministic Mealy automata with n states outputting ternary strings.

Original entry on oeis.org

3, 12, 54, 210, 798, 2850, 10038, 34410, 116406, 388362, 1283430, 4203786, 13675038, 44211570, 142202574, 455299242, 1451997726, 4614253122, 14617620726, 46177325994, 145505603694, 457437342546, 1435074324006, 4493508791754, 14045385985902

Offset: 1

Lucas B. Vieira, Mar 02 2024

nonn

a(n) counts the minimal number of ternary words w = uv, with |w| = n, such that u is an irreducible prefix and v a primitive word. This defines a minimal "pattern", written as "u(v)", describing the behavior of a minimal n-state deterministic Mealy automaton outputting a string from a ternary alphabet, where u is the transient output, and v the cyclic output, possibly truncated. Used in the definition of the Deterministic Complexity (DC) of strings (Vieira and Budroni, 2022).

			a(1) = 3 as there are only 3 deterministic Mealy automata with 1 state producing ternary words, corresponding to the 3 patterns (0), (1) and (2), generating the strings w=0^L, w=1^L, and w=2^L for L >= 1.
a(2) = 12, since there are 12 minimal ternary patterns: (01), 0(1), (02), 0(2), (10), 1(0), (12), 1(2), (20), 2(0), (21), 2(1).
E.g.: The ternary string w = 000120120 can be described by the pattern 00(012), where the parentheses indicate the repeating part, up to truncation. This pattern is minimal, with 5 symbols (ignoring the parentheses). It describes the behavior of a minimal deterministic Mealy automaton producing the string w, leading to its Deterministic Complexity (DC) to be DC(w) = 5.

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, f_1(n).

Lucas B. Vieira and Costantino Budroni, Temporal correlations in the simplest measurement sequences, Quantum 6 p. 623 (2022).

Cf. A059412 for the case of binary strings.

Cf. A143324 for psi(k,n).

NumPrimitiveWords[k_, n_] := Sum[MoebiusMu[d] k^(n/d), {d, Divisors[n]}];
a[n_] := NumPrimitiveWords[3, n] + Sum[(3 - 1) 3^(i - 1) NumPrimitiveWords[3, n - i], {i, 1, n - 1}]

a(n) = psi(3, n) + Sum_{i=1..n-1} (3-1)*3^(i-1)*psi(3, n-i), where psi(k,n) is the number of primitive words of length n on a k-letter alphabet (Cf. A143324).

A129622 Number of minimal deterministic finite automata (DFA) with n states on a two-letter alphabet.

Original entry on oeis.org

0, 2, 24, 1028, 56014, 3705306, 286717796, 25493886852

Offset: 0

Johnicholas Hines (johnicholas.hines(AT)gmail.com), May 30 2007

DFAs are counted up to equivalence, where two DFAs are equivalent if they recognize the same language. Therefore, a(n) is the number of languages on {a,b} recognizable by a minimal complete DFA of n states. A minimal DFA is one which is not equivalent to any smaller DFA. - Arthur O'Dwyer, Jul 26 2024

A DFA requires at least one state: the initial state. Since there are no DFAs with zero states, a(0)=0. - Arthur O'Dwyer, Jul 26 2024

			From _Arthur O'Dwyer_, Jul 26 2024: (Start)
For n=1 the a(1)=2 distinct DFAs are
  State 1: a->1, b->1
  State 1: a->1, b->1, accepting
The first of these accepts the empty language; the second accepts the universal language.
For n=3, the following two DFAs are equivalent, since they accept the same language:
  State 1: a->2, b->2, accepting; State 2: a->1, b->3; State 3: a->2, b->2
  State 1: a->3, b->3, accepting; State 2: a->3, b->3; State 3: a->1, b->2
The following DFA is not counted at all, because it is minimizable to (that is, accepts the same language as) a two-state DFA:
  State 1: a->1, b->2; State 2: a->2, b->3, accepting; State 3: a->3, b->2, accepting
(End)

M. Almeida, N. Moreira, and R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007) 93-102, gives a(7) in Section 5.
Frederique Bassino, Julien David and Cyril Nicaud, REGAL: a library to randomly and exhaustively generate automata, also at HAL-00459643.
Michael Domaratzki, Derek Kisman, and Jeffrey Shalit. On the number of distinct languages accepted by finite automata with n states, Journal of Automata, Languages and Combinatorics 7 (2002) 4-18, Section 6, a(n) = f_2(n).

Cf. A059412, A000282.

A059412(n) <= a(n). - Arthur O'Dwyer, Jul 26 2024

a(0)=0 and a(1)=2 prepended by Arthur O'Dwyer, Jul 26 2024

A331120 Number of non-isomorphic minimal deterministic finite automata with n transient states recognizing a finite binary language.

Original entry on oeis.org

1, 1, 6, 60, 900, 18480, 487560, 15824880, 612504240, 27619664640, 1425084870240, 82937356685760, 5381249970008640, 385518151040336640, 30248651895457718400, 2581418447382311243520, 238181756821410417488640, 23637327769847150582661120, 2511570244361817605178754560, 284573826857792109743033564160

Offset: 0

Michael Wallner, Jan 10 2020

nonn

Using parking functions, Priez obtained an exact enumerative formula for the number of non-isomorphic minimal deterministic finite automata (MADFA) with n states recognizing a finite language over an alphabet of size k > 0 (Priez, 2015). An exact generation of MADFAs is given by Almeida et al. (2008). In that paper, exact enumerative formulae for the number of MADFA with n states for 1 < n < 6 and any alphabet size are also presented. - Nelma Moreira, Mar 08 2021

Marco Almeida, Nelma Moreira, and Rogério Reis, Exact Generation of Minimal Acyclic Deterministic Finite Automata. Int. J. Found. Comput. Sci. 19(4): 751-765 (2008).
Manosij Ghosh Dastidar and Michael Wallner, Asymptotics of relaxed k-ary trees, arXiv:2404.08415 [math.CO], 2024. See p. 1.6.
Michael Domaratzki, Derek Kisman, and Jeffrey Shallit, On the number of distinct languages accepted by finite automata with n states, J. Autom. Lang. Combinat. (2002) Vol. 77 No. 4, 469-486. See Section 6, f'_2(n).
Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height, arXiv:1703.10031 [math.CO], 2017.
Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height, J. Combin. Theory Ser. A, 172:105177, 2020.
Andrew Elvey Price, Wenjie Fang, and Michael Wallner, Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 11:1-11:13.
Jean-Baptiste Priez, Enumeration of minimal acyclic automata via generalized parking functions. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp. 697-708. hal-01337781.

Cf. A059412 (minimal unary DFAs).
A082161 (2^(n-1)*A082161(n)) is an upper bound; furthermore these are not necessarily minimal but acyclic binary DFAs without (!) accepting states.
A288950 (2^(n-1)*A288950(n)) is a lower bound.

a(n) = b(n,n), where the sequence b(n,m) = 2*b(n,m-1) + (m+1)*b(n-1,m) - m*b(n-2,m-1) for n >= m > 1, b(n,1) = b(n,0) + 2*b(n-1,1) for n >= 1, b(n,0) = 1 for n >= 0.

For any k > 0, m(k,n) with m(k,1)=1 and s(2*m^k-1,n) = Sum_{t=1..n} (binomial(n-1,t-1) * s(2*(m+t)^k-t-1,n-t) * m(k,t)) where s(x,n) enumerates x-parking functions (Priez, 2015). - Nelma Moreira, Mar 08 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Maple

Mathematica

Formula

A284462 Number of length-n binary strings s whose longest repeated suffix appears exactly twice in s.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Extensions

A370489 Deterministic complexity of binary strings, in shortlex order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A370821 Number of minimal deterministic Mealy automata with n states outputting ternary strings.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A129622 Number of minimal deterministic finite automata (DFA) with n states on a two-letter alphabet.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A331120 Number of non-isomorphic minimal deterministic finite automata with n transient states recognizing a finite binary language.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula