login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006690 Number of deterministic, completely-defined, initially-connected finite automata with 3 inputs and n unlabeled states.
(Formerly M5316)
8
1, 56, 7965, 2128064, 914929500, 576689214816, 500750172337212, 572879126392178688, 835007874759393878655, 1510492370204314777345000, 3320470273536658970739763334, 8718034433102107344888781813632, 26945647825926481227016730431025962, 96843697086370972449408988324175689680 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

Found in column 0 of triangle A107676, which is the matrix cube of triangle A107671 (see recurrence formulas). - Paul D. Hanna, Jun 07 2005

A complete initially connected deterministic finite automaton (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, Jul 31 2005

This is H_3(n) in Liskovets (DAM, Vol. 154, 2006), p. 548; the formula for H_k is given in Eq. (11), p. 546. - M. F. Hasler, May 16 2018

REFERENCES

R. Bacher and 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

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..14.

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.

M. Almeida, N. Moreira, R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007), 93-102; see B(k=3,n).

Valery A. Liskovets, The number of connected initial automata, Kibernetika (Kiev), 3 (1969), 16-19 (in Russian; English translation: Cybernetics, 4 (1969), 259-262).

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

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

Robert W. Robinson, Counting strongly connected finite automata, pages 671-685 in "Graph theory with applications to algorithms and computer science." Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4-8, 1984. Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. Wall. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1985. xv+810 pp. ISBN: 0-471-81635-3; Math Review MR0812651. (86g:05026). [Annotated scanned copy, with permission of the author.]

FORMULA

a(n) = h_3(n)/(n-1)!, where h_3(1) := 1, h_3(n) := n^(3*n) - Sum_{i=1..n-1} binomial(n-1, i-1) * n^(3*n-3*i) * h_3(i) for n > 1.

For k = 3, a(n) = Sum (Product_{i=1..n-1} i^(f_i - f_{i-1} - 1))) * n^(n*k - f_{n-1} - 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, Jul 31 2005 [Typo corrected by Petros Hadjicostas, Mar 06 2021. See Theorem 8 in Almeida, Moreira, and Reis (2007). The value of f_0 is not relevant.]

MAPLE

b := proc(k, n)

    option remember;

    if n = 1 then

        1;

    else

        n^(k*n) -add(binomial(n-1, j-1)*n^(k*(n-j))*procname(k, j), j=1..n-1) ;

    end if;

end proc:

B := proc(k, n)

    b(k, n)/(n-1)! ;

end proc:

A006690 := proc(n)

    B(3, n) ;

end proc:

seq(A006690(n), n=1..10) ; # R. J. Mathar, May 21 2018

MATHEMATICA

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

PROG

(PARI) {a(n)=local(P=matrix(n+1, n+1, r, c, if(r>=c, (r^3)^(r-c)/(r-c)!)), D=matrix(n+1, n+1, r, c, if(r==c, r))); (P^-1*D^3*P)[n+1, 1]} \\ Paul D. Hanna, Jun 07 2005

(PARI) A6690=[1]; A006690(n)={for(n=#A6690+1, n, A6690=concat(A6690, n^(3*n)/(n-1)!-sum(k=1, n-1, n^(3*k)*A6690[n-k]/k!))); A6690[n]} \\ M. F. Hasler, May 16 2018

CROSSREFS

Cf. A006689, A006689, A107671, A107676.

Sequence in context: A233428 A183614 A082167 * A202922 A034204 A275921

Adjacent sequences:  A006687 A006688 A006689 * A006691 A006692 A006693

KEYWORD

easy,nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

a(11) and more detailed definition from Valery A. Liskovets, Apr 09 2003

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

More terms from M. F. Hasler, May 16 2018

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 1 11:25 EST 2021. Contains 349429 sequences. (Running on oeis4.)