A054745 Number of nonisomorphic binary n-state automata without output under input permutations.

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

Alois P. Heinz, Table of n, a(n) for n = 0..45

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

Cf. A001372, A054050, A054732, A054746.

Sequence in context: A098118 A097821 A337387 * A323322 A356589 A326221

Adjacent sequences: A054742 A054743 A054744 * A054746 A054747 A054748

Keyword

nonn

Author

Vladeta Jovovic, Apr 22 2000

Extensions

More terms from Alois P. Heinz, Aug 15 2014

Status

approved