A054747 Number of inequivalent n-state 2-input 2-output automata with respect to an input permutation.

3, 76, 4003, 352744, 41876694, 6217447912, 1106509486839, 229553329028386, 54393886281136386, 14493994916221695566, 4289933406949379595583, 1396384878753272032544946, 495758886710258565409900342, 190649910996342815795394676340, 78947451456044942567072721038672, 35023754187171124856459358053765838

Offset

1,1

References

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

Links

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

Michael A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [See Theorem 6.2 with k = p = 2 (p. 107) and Table IV (p. 112).]

Prog

(PARI) A054747(n)={local(p=vector(n)); local(q=matrix(2, 2)); q[1, 1] = 2; q[1, 2] = 0; q[2, 1]=0; q[2, 2]=1; my(S=0, A() = sum(j=1, 2, prod(r=1, n, prod(s=1, 2, (2*sumdiv(lcm(r, s), d, if(d < n+1, d*p[d], 0)))^(p[r]*q[j, s]*gcd(r, s)))))/2,
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, A054732.

Euler transform of A000282.

Sequence in context: A201428 A141103 A300386 * A302375 A232030 A054950

Adjacent sequences: A054744 A054745 A054746 * A054748 A054749 A054750

Keyword

nonn

Author

Vladeta Jovovic, Apr 22 2000

Extensions

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

Status

approved