login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006689 Number of deterministic, completely-defined, initially-connected finite automata with 2 inputs and n unlabeled states.
(Formerly M4876)
5
1, 12, 216, 5248, 160675, 5931540, 256182290, 12665445248, 705068085303, 43631250229700, 2970581345516818, 220642839342906336, 17753181687544516980, 1538156947936524172656, 142767837727544113783650 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

a(n) is divisible by n^2, see A082166. These automata have no nontrivial automorphisms (by states).

Equals the first column of triangle A107670, which is the matrix square of triangle A107667. As a lower triangular matrix T, A107667 satisfies: T = D + SHIFT_LEFT(T^2) where SHIFT_LEFT shifts each row 1 place left and D is the diagonal matrix [1,2,3,...]. - Paul D. Hanna, May 19 2005

A complete initially connected deterministic finite automata (icdfa) with n states in an alphabet of k symbols can be represented by a special string of {0,...,n-1}^* with length kn. In that string, let f_i be the index of the first occurrence of state i (used in the formula). - Nelma Moreira (nam(AT)ncc.up.pt), Jul 31 2005

REFERENCES

R. Bacher, C. Reutenauer, The number of right ideals of given codimension over a finite field, in Noncommutative Birational Geometry, Representations and Combinatorics, edited by Arkady. Berenstein and Vladimir. Retakha, Contemporary Mathematics, Vol. 592, 2013.

V. A. Liskovets, The number of initially connected automata, Kibernetika, (Kiev), No3 (1969), 16-19; Engl. transl.: Cybernetics, v.4 (1969), 259-262.

R. Reis, N. Moreira and M. Almeida, On the Representation of Finite Automata, in Proocedings of 7th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS05) Jun 30, 2005, Como, Italy, page 269-276

Robert W. Robinson, Counting strongly connected finite automata, pp. 671-685 of Y. Alavi et al., eds., Graph Theory, Combinatorics and Applications. Wiley, NY, 2 vols., 1991.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Table of n, a(n) for n=1..15.

M. Almeida, N. Moreira and R. Reis. On the Representation of Finite Automata, Technical Report DCC-2005-04, DCC - FC & LIACC, Universidade do Porto, April, 2005.

E. Lebensztayn, A large deviations principle for the Maki-Thompson rumour model, arXiv preprint arXiv:1411.5614 [math.PR], 2014-2015.

V. A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.

V. A. Liskovets, Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, No.3 (2006), 537-551.

FORMULA

a(n) = h_2(n)/(n-1)! where h_2(1) := 1, h_2(n) := n^(2*n)-sum(binomial(n-1, i-1)*n^(2*n-2*i)*h_2(i), i=1..n-1), n>1.

For k=2, a(n) = sum(prod(i=1..n-1, i^{f_i - f_{i-1} -1})*n^{n*k-f_{n-1}}) where the sum is taken over integers f_1, ..., f_{n-1} satisfying 0<=f_1 < k and f_{i-1}< f_{i} <i*k for i = 2..n-1. - Nelma Moreira (nam(AT)ncc.up.pt), Jul 31 2005

EXAMPLE

a(2)=12 since the following transition diagrams represent all twelve initially connected automata with two input letters x and y and two states 1 (initial) and 2: 1==x,y==>2==>, 1--x-->2==>, 1--y-->2==>, 1--y-->1 1--x-->1 where the transitions from state 2 are specified arbitrary (4 different possibilities in every case).

MATHEMATICA

a[1] = 1; a[n_] := a[n] = n^(2*n)/(n-1)! - Sum[n^(2*(n-i))*a[i]/(n-i)!, {i, 1, n-1}]; Table[ a[n], {n, 1, 15}] (* Jean-Fran├žois Alcover, Dec 15 2014 *)

PROG

(PARI) a(n)=if(n<1, 0, n^(2*n)/(n-1)!-sum(i=1, n-1, n^(2*(n-i))/(n-i)!*a(i)))

(PARI) a(n)=local(A); if(n<1, 0, A=n*x+x*O(x^n); for(k=0, n, A+=polcoeff(A, k)*x^k*(n-prod(i=0, k, 1-(n-i)*x))); polcoeff(A, n))

CROSSREFS

Cf. A006690, A107670, A107667.

Sequence in context: A119309 A034788 A082165 * A009176 A087585 A214512

Adjacent sequences:  A006686 A006687 A006688 * A006690 A006691 A006692

KEYWORD

easy,nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms and more detailed definition from Valery A. Liskovets, Apr 09 2003

Further terms from Paul D. Hanna, May 19 2005

Edited by N. J. A. Sloane, Dec 06 2008 at the suggestion of R. J. Mathar

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 20 15:44 EDT 2017. Contains 293626 sequences.