VOOZH about

URL: https://oeis.org/A054745

⇱ A054745 - OEIS

login
A054745
Number of nonisomorphic binary n-state automata without output under input permutations.
13
1, 1, 7, 74, 1474, 41876, 1540696, 68343112, 3540691525, 209612916303, 13957423192794, 1032436318269648, 83993175608894096, 7453446303042245261, 716451740543945788671, 74159075140708644544128, 8223831291824019614386868, 972718473204236819072891710
OFFSET
0,3
COMMENTS
Also isomorphism classes of unordered pairs of endofunctions i.e. an unorder pair {f,g} of functions from {1,...,n} to itself. - Christian G. Bower, Dec 18 2003
REFERENCES
F. Harary and E. Palmer, Graphical Enumeration, 1973.
LINKS
M. A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, 1965, p. 110.
FORMULA
a(n) = sum {1*s_1+2*s_2+...=n, 1*t_1+2*t_2=2} (fixA[s_1, s_2, ...;t_1, t_2]/(1^s_1*s_1!*2^s_2*s_2!*...*1^t_1*t_1!*2^t_2*t_2!)) where fixA[...] = prod {i, j>=1} ( (sum {d|lcm(i, j)} (d*s_d))^(gcd(i, j)*s_i*t_j)). - Christian G. Bower, Dec 18 2003
MAPLE
with(numtheory):
b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
{seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
end:
a:= proc(n) option remember; add(add(mul(mul(add(coeff(s, x, d)
*d, d=divisors(ilcm(i, j)))^(igcd(i, j)*coeff(s, x, i)*
coeff(t, x, j)), j=1..degree(t)), i=1..degree(s))
/mul(i^coeff(t, x, i)*coeff(t, x, i)!, i=1..degree(t))
/mul(i^coeff(s, x, i)*coeff(s, x, i)!, i=1..degree(s))
, t=b(2$2)), s=b(n$2))
end:
seq(a(n), n=0..20); # Alois P. Heinz, Aug 15 2014
MATHEMATICA
b[n_, i_] := b[n, i] = If[n==0, {0}, If[i<1, {}, Table[Map[Function[{p}, p + j*x^i], b[n - i*j, i-1]], {j, 0, n/i}] // Flatten // Union]];
a[n_] := a[n] = Sum[Sum[Product[Product[With[{g = GCD[i, j]*Coefficient[s, x, i]*Coefficient[t, x, j]}, If[g==0, 1, Sum[Coefficient[s, x, d]*d, {d, Divisors[LCM[i, j]]}]^g]], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/
Product[i^Coefficient[t, x, i]Coefficient[t, x, i]!, {i, Exponent[t, x]}]/
Product[i^Coefficient[s, x, i]Coefficient[s, x, i]!, {i, Exponent[s, x]}], {t, b[2, 2]}], {s, b[n, n]}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 16 2015, after Alois P. Heinz, updated Jan 01 2021 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladeta Jovovic, Apr 22 2000
EXTENSIONS
More terms from Alois P. Heinz, Aug 15 2014
STATUS
approved