A054050 Number of nonisomorphic binary n-state automata.

1, 10, 129, 2836, 83061, 3076386, 136647824, 7081061404, 419223006090, 27914819962058, 2064872379041701, 167986348586006675, 14906892578198245332, 1432903480780688968334, 148318150277923875087238, 16447662583606982784243526, 1945436946407977282783367806, 244476687257496605058725664611

Offset: 1

Author

Vladeta Jovovic, Apr 29 2000

Keywords

• nonn

Comments

Also, number of isomorphism classes of ordered pairs of endofunctions (i.e., an order pair (f,g) of functions) from {1,...,n} to itself. - Christian G. Bower, Dec 18 2003

Examples

			From _Petros Hadjicostas_, Mar 08 2021: (Start)
For n = 2, we have the partitions 1*2 + 2*0 and 1*0 + 2*1 of 2 (in frequency notation). The corresponding denominators in _Christian G. Bower_'s formula are 1^2*2!*2^0*0! = 2 and 1^0*0!*2^1*1! = 2.
Also, fixA[s_1 = 2, s_2 = 0] = (Sum_{d|1} d*s_d)^(2*s_1) * (Sum_{d|2} d*s_d)^(2*s_2) = (1*s_1)^(2*s_1) = 16. In addition, fixA[s_1 = 0, s_2 = 1] = (Sum_{d|1} d*s_d)^(2*s_1) * (Sum_{d|2} d*s_d)^(2*s_2) = (1*s_1 + 2*s_2)^(2*s_2) = (0 + 2)^2 = 4. Hence a(2) = 16/2 + 4/2 = 10. (End)
		

References

• F. Harary and E. Palmer, Graphical Enumeration, 1973.

Links

• M. A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [See p. 107 (Theorem 6.1 with k = 2 and p = 1) and p. 110 (Table I).]

Crossrefs

Cf. A001372, A002854, A054745, A054051.

Programs

PARI

A054050(n)={local(p=vector(n));
my(S=0, A() = prod(i=1, n, sumdiv(i, d, d*p[d])^(2*p[i])),
inc()=!forstep(i=n, 1, -1, p[i]n, p[i]=n); next(2))); t==n && S+ = A()/prod(i=1, n, i^p[i]*p[i]!)); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 08 2021

Formula

a(n) = Sum_{1*s_1+2*s_2+...=n} fixA[s_1, s_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...), where fixA[s_1, s_2, ...] = Product_{i>=1} (Sum_{d|i} d*s_d)^(2*s_i). - Christian G. Bower, Dec 18 2003 [Corrected by Petros Hadjicostas, Mar 08 2021 using Theorem 6.1 in Harrison (1965) with k = 2 inputs and p = 1 output.]

Extensions

a(16)-a(18) from Petros Hadjicostas, Mar 08 2021