A059413 -id:A059413 - cp's OEIS frontend

A059412 Number of distinct minimal unary DFA's with exactly n states.

2, 4, 12, 30, 78, 180, 432, 978, 2220, 4926, 10908, 23790, 51750, 111564, 239604, 511758, 1089306, 2309118, 4880946, 10285146, 21619770, 45334776, 94865904, 198116082, 413013684, 859573638, 1786263822, 3706729488, 7681910826

Offset: 1

Jeffrey Shallit, Jan 30 2001

nonn

Also, number of binary strings w of length 2n such that the longest suffix of w appearing at least twice in w is of length n. - Jeffrey Shallit, Mar 20 2017
Also, number of ultimately periodic binary sequences uvvvv... with |u|+|v| = n, formula uses psi(|v|) and 2^(|u|-1), plus psi(n) for u empty. - Michael Vielhaber, Mar 19 2022
Also, number of minimal length-n binary patterns, each corresponding to a minimal n-state deterministic Mealy automaton outputting some binary string. Used in the definition of the Deterministic Complexity (DC) of a string w, i.e., DC(w) = n. - Lucas B. Vieira, Mar 02 2024

			a(1) = 2 because there are exactly two minimal unary automata with 1 state.

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).
Jeffrey Shallit, Notes on Enumeration of Finite Automata, manuscript, Jan 30, 2001.

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.
Lucas B. Vieira and Costantino Budroni, Temporal correlations in the simplest measurement sequences, Quantum 6 p. 623 (2022).
Lucas Vieira Barbosa, Nonclassical Temporal Correlations Under Finite-Memory Constraints, Doctoral Thesis, Univ. Wien (Austria 2024). See p. 35.

A059412 := proc(n)
    A027375(n)+add(A027375(n-j)*2^(j-1),j=1..n-1) ;
end proc:
seq(A059412(n),n=1..10) ; # R. J. Mathar, May 21 2018

A027375[n_] := DivisorSum[n, MoebiusMu[n/#]*2^# &];
a[n_] := A027375[n] + Sum[A027375[n-j]*2^(j-1), {j, 1, n-1}];
Table[a[n], {n, 1, 29}] (* Jean-François Alcover, May 08 2023 *)

mypsi(n) = sumdiv(n, d, moebius(n/d)*2^d) /* from A027375 */
a(n) = mypsi(n) + sum(j=1, n-1, mypsi(n-j)*2^(j-1)) \\ Michel Marcus, May 25 2013

a(n) = psi(n) + Sum_{j=1..n-1} psi(n-j)*2^(j-1), where psi(n) is the number of primitive words of length n over a 2-letter alphabet (expressible in terms of the Moebius function).

a(n) = A027375(n) + A059413(n-1). - R. J. Mathar, May 21 2018

A192088 Number of permutations of [n] realized by the shift on 3 letters.

Original entry on oeis.org

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

Sergi Elizalde, Jun 23 2011

nonn

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

Sergi Elizalde, The number of permutations realized by a shift, arXiv:0909.2274v1 [math.CO]

Cf. A059413.

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.

A192089 Number of permutations of [n] that require a 3-letter alphabet in order to be realized by a shift.

Original entry on oeis.org

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

Offset: 2

Sergi Elizalde, Jun 23 2011

nonn

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

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

			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

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

Sergi Elizalde, The number of permutations realized by a shift, arXiv:0909.2274v1 [math.CO]

Equals A192088 minus A059413

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.

cp's OEIS Frontend

A059412 Number of distinct minimal unary DFA's with exactly n states.

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Maple

Mathematica

PARI

Formula

A192088 Number of permutations of [n] realized by the shift on 3 letters.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A192089 Number of permutations of [n] that require a 3-letter alphabet in order to be realized by a shift.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula