login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054732 Number of inequivalent n-state 2-input 2-output automata with respect to input and output permutations. 8
2, 44, 2038, 176936, 20943790, 3108818680, 553255960308, 114776687721990, 27196943499525498, 7246997465494260922, 2144966703605620242622, 698192439379511764136358, 247879443355186031710674326, 95324955498172729163827175460, 39473725728022499730768584065928, 17511877093585563126312782917277602 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
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).]
PROG
(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\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.
Sequence in context: A161744 A208045 A267070 * A161722 A290879 A054914
KEYWORD
nonn
AUTHOR
Vladeta Jovovic, Apr 22 2000
EXTENSIONS
Terms a(14)-a(16) from Petros Hadjicostas, Mar 08 2021
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 21:54 EDT 2024. Contains 371254 sequences. (Running on oeis4.)