A054732 Number of inequivalent n-state 2-input 2-output automata with respect to input and output permutations.

2, 44, 2038, 176936, 20943790, 3108818680, 553255960308, 114776687721990, 27196943499525498, 7246997465494260922, 2144966703605620242622, 698192439379511764136358, 247879443355186031710674326, 95324955498172729163827175460, 39473725728022499730768584065928, 17511877093585563126312782917277602

Offset: 1

Author

Vladeta Jovovic, Apr 22 2000

Keywords

• nonn

Comments

From Petros Hadjicostas, Mar 08 2021: (Start)

The PARI program below implements the formula in Theorem 6.3 (p. 108) in Harrison (1965) with k = 2 inputs and p = 2 outputs. We use the partitions of 2 twice.

All partitions in the program are written in frequency or multiplicity notation (so, the partitions of 2 are written as 1*2 + 2*0 and 1*0 + 2*1; see the matrices q and qq in the program).

If (s_1, ..., s_n) is a partition of n in frequency notation (with s_i >= 0 for all i and Sum_{i=1..n} i*s_i = n) and we need an element s_j with j > n, we define it to be 0. That is why we use sumdiv(lcm(r, s), d, if(d < n+1, d*p[d], 0)) and sumdiv(lcm(r, s), d, if(d < 3, d*qq[jj, d], 0)) in the program. (End)

References

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

Links

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

Crossrefs

Cf. A002854.

Programs

PARI

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

Extensions

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