cp's OEIS Frontend

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

%I A054732 #19 Mar 08 2021 22:50:49
%S A054732 2,44,2038,176936,20943790,3108818680,553255960308,114776687721990,
%T A054732 27196943499525498,7246997465494260922,2144966703605620242622,
%U A054732 698192439379511764136358,247879443355186031710674326,95324955498172729163827175460,39473725728022499730768584065928,17511877093585563126312782917277602
%N A054732 Number of inequivalent n-state 2-input 2-output automata with respect to input and output permutations.
%C A054732 From _Petros Hadjicostas_, Mar 08 2021: (Start)
%C A054732 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.
%C A054732 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).
%C A054732 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)
%D A054732 F. Harary and E. Palmer, Graphical Enumeration, 1973.
%H A054732 Michael A. Harrison, <a href="http://dx.doi.org/10.4153/CJM-1965-010-9">A census of finite automata</a>, Canad. J. Math., 17, No. 1, (1965), 100-113. [See Theorem 6.3 (p. 108) with k = p = 2 and Table V (p. 112).]
%o A054732 (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;
%o A054732 qq[1, 1] = 2; qq[1, 2] = 0; qq[2, 1]=0; qq[2, 2]=1;
%o A054732 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,
%o A054732 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
%Y A054732 Cf. A002854.
%K A054732 nonn
%O A054732 1,1
%A A054732 _Vladeta Jovovic_, Apr 22 2000
%E A054732 Terms a(14)-a(16) from _Petros Hadjicostas_, Mar 08 2021