|
|
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
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|