A054052 Number of nonisomorphic n-state automata with binary inputs and outputs.

4, 136, 7860, 703760, 83731616, 12434579448, 2213014106124, 459106576445584, 108787771126443552, 28987989805582701000, 8579866813375037411844, 2792769757495835238342624, 991517773420290134796904064, 381299821992680629261308708504, 157894902912089771345216547890976, 70047508374342247037912201234627760

Offset

1,1

References

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

Links

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

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 = p = 2) and p. 112 (Table III).]

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} 2*d*s_d)^(2*s_i). - [Modified from Christian G. Bower's contribution in A054050 by Petros Hadjicostas, Mar 08 2021 using Theorem 6.1 in Harrison (1965) with k = 2 inputs and p = 2 outputs.]

Prog

(PARI) A054052(n) = {local(p=vector(n)); my(S=0, A() = prod(i=1, n, sumdiv(i, d, 2*d*p[d])^(2*p[i])), inc()=!forstep(i=n, 1, -1, p[i]<n\i && p[i]++ && return; p[i]=0), t); until(inc(), t=0; for( i=1, n, if( n < t+=i*p[i], until(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

Crossrefs

Cf. A002854, A054050, A054747, A054732, A054053.

Sequence in context: A202299 A024264 A012052 * A012070 A366446 A001374

Adjacent sequences: A054049 A054050 A054051 * A054053 A054054 A054055

Keyword

nonn

Author

Vladeta Jovovic, Apr 29 2000

Extensions

Terms a(14)-a(16) from Petros Hadjicostas, Mar 08 2021.

Status

approved