A054732 -id:A054732 - cp's OEIS frontend

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

Vladeta Jovovic, Apr 22 2000

nonn

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

F. Harary and E. Palmer, Graphical Enumeration, 1973.

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.

Cf. A001372, A054050, A054732, A054746.

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

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 *)

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

More terms from Alois P. Heinz, Aug 15 2014

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

Original entry on oeis.org

1, 6, 67, 1379, 40000, 1488212, 66468616, 3459744878, 205517092374, 13719689837415, 1016860316477931, 82855990193202263, 7361905026684383986, 708398087768889272827, 73390382551302560225067, 8144731151602797676232825, 963990026196934640329291135

Offset: 1

Vladeta Jovovic, Apr 22 2000

nonn

Inverse Euler transform of A054745.

			There are 40000 nonisomorphic connected binary 5-state automata under input permutations.

F. Harary and E. Palmer, Graphical Enumeration, 1973.

Alois P. Heinz, Table of n, a(n) for n = 1..45
M. A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, 1965, p. 110.

Cf. A054732, A027834.

More terms from Alois P. Heinz, Feb 20 2017

A000282 Finite automata.

Original entry on oeis.org

3, 70, 3783, 338475, 40565585, 6061961733, 1083852977811, 225615988054171, 53595807366038234, 14308700593468127485, 4241390625289880226714, 1382214286200071777573643, 491197439886557439295166226, 189044982636675290371386547592, 78334771617452038208125184627931, 34771576300926271400714044414858372

Offset: 1

N. J. A. Sloane

nonn

Given the name of A054747, another name for this sequence can be "Number of inequivalent n-state 2-input 2-output connected automata with respect to an input permutation." - Petros Hadjicostas, Mar 08 2021

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Christian G. Bower, PARI programs for transforms, 2007.
Michael A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [First apply Theorem 6.2 (p. 107) with k = p = 2 to get A054747. Then apply Theorem 7.2 (p. 110) to get the number of classes of connected automata counted by A054747. - _Petros Hadjicostas_, Mar 08 2021]
N. J. A. Sloane, Maple programs for transforms, 2001-2020.

Cf. A002854, A054732, A054747.

/* This program is a modification of Christian G. Bower's PARI program for the inverse Euler transform from the link above. */
lista(nn) = {local(A=vector(nn+1)); for(n=1, nn+1, A[n]=if(n==1, 1, A054747(n-1))); local(B=vector(#A-1,n,1/n),C); A[1] = 1; C = log(Ser(A)); A=vecextract(A,"2.."); for(i=1, #A, A[i] = polcoeff(C,i)); A = dirdiv(A,B); } \\ Petros Hadjicostas, Mar 08 2021

Inverse Euler transform of A054747. - Petros Hadjicostas, Mar 08 2021

More terms from Vladeta Jovovic, Apr 22 2000

Terms a(14)-a(16) from Petros Hadjicostas, Mar 08 2021

A054052 Number of nonisomorphic n-state automata with binary inputs and outputs.

Original entry on oeis.org

4, 136, 7860, 703760, 83731616, 12434579448, 2213014106124, 459106576445584, 108787771126443552, 28987989805582701000, 8579866813375037411844, 2792769757495835238342624, 991517773420290134796904064, 381299821992680629261308708504, 157894902912089771345216547890976, 70047508374342247037912201234627760

Offset: 1

Vladeta Jovovic, Apr 29 2000

nonn

F. Harary and E. Palmer, Graphical Enumeration, 1973.

M. A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [See p. 107 (Theorem 6.1 with k = p = 2) and p. 112 (Table III).]

Cf. A002854, A054050, A054747, A054732, A054053.

A054052(n) = {local(p=vector(n)); my(S=0, A() = prod(i=1, n, sumdiv(i, d, 2*d*p[d])^(2*p[i])), inc()=!forstep(i=n, 1, -1, p[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

a(n) = Sum_{1*s_1+2*s_2+...=n} fixA[s_1, s_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...), where fixA[s_1, s_2, ...] = Product_{i>=1} (Sum_{d|i} 2*d*s_d)^(2*s_i). - [Modified from Christian G. Bower's contribution in A054050 by Petros Hadjicostas, Mar 08 2021 using Theorem 6.1 in Harrison (1965) with k = 2 inputs and p = 2 outputs.]

Terms a(14)-a(16) from Petros Hadjicostas, Mar 08 2021.

A054747 Number of inequivalent n-state 2-input 2-output automata with respect to an input permutation.

Original entry on oeis.org

3, 76, 4003, 352744, 41876694, 6217447912, 1106509486839, 229553329028386, 54393886281136386, 14493994916221695566, 4289933406949379595583, 1396384878753272032544946, 495758886710258565409900342, 190649910996342815795394676340, 78947451456044942567072721038672, 35023754187171124856459358053765838

Offset: 1

Vladeta Jovovic, Apr 22 2000

nonn

F. Harary and E. Palmer, Graphical Enumeration, 1973.

Michael A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [See Theorem 6.2 with k = p = 2 (p. 107) and Table IV (p. 112).]

Cf. A002854, A054732.

Euler transform of A000282.

A054747(n)={local(p=vector(n)); local(q=matrix(2,2)); q[1,1] = 2; q[1,2] = 0; q[2,1]=0; q[2,2]=1; my(S=0, A() = sum(j=1, 2, prod(r=1, n, prod(s=1, 2, (2*sumdiv(lcm(r,s), d, if(d < n+1, d*p[d], 0)))^(p[r]*q[j,s]*gcd(r,s)))))/2,
inc()=!forstep(i=n, 1, -1, p[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

Terms a(14)-a(16) from Petros Hadjicostas, Mar 08 2021

A054748 Number of inequivalent n-state 1-input n-output automata.

Original entry on oeis.org

1, 6, 29, 209, 1652, 15981, 171837, 2060481, 26951143, 381398614, 5789262973, 93674732887, 1607249998772, 29114205685585, 554699253112833, 11079840198856480, 231366880421810416, 5038182952520057443, 114152394913959017721, 2685768694808159100283

Offset: 1

Vladeta Jovovic, Apr 22 2000

nonn

F. Harary and E. Palmer, Graphical Enumeration, 1973.

M. A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, 1965, 100-113.
Sean A. Irvine, Java program (github)

Cf. A054732, A054749.

Euler transform of A054749.

More terms from Sean A. Irvine, Feb 21 2022

A054742 Finite automata.

Original entry on oeis.org

2, 41, 1952, 172043, 20511924, 3058135804, 545880769246, 113492835877474, 26936031159146324, 7186257876123323136, 2129016419091882758064, 693526953186674417975860, 246375213208005330322801608, 94795009032593187381371471299, 39271207630529921493096501099998, 17428450442901657489782698628853383, 8249301503003544171210026750727519638

Offset: 1

Vladeta Jovovic, Apr 22 2000

nonn

F. Harary and E. Palmer, Graphical Enumeration, 1973.

Christian G. Bower, PARI programs for transforms, 2007.
Michael A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [See Table V, p. 112.]

Inverse Euler transform of A054732.

/* This program is a modification of Christian G. Bower's PARI program for the inverse Euler transform from the link above. */
lista(nn) = {local(A=vector(nn+1)); for(n=1, nn+1, A[n]=if(n==1, 1, A054732(n-1))); local(B=vector(#A-1, n, 1/n), C); A[1] = 1; C = log(Ser(A)); A=vecextract(A, "2.."); for(i=1, #A, A[i] = polcoeff(C, i)); A = dirdiv(A, B); } \\ Petros Hadjicostas, Mar 08 2021

Terms a(14)-a(17) from Petros Hadjicostas, Mar 08 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A000282 Finite automata.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A054052 Number of nonisomorphic n-state automata with binary inputs and outputs.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A054747 Number of inequivalent n-state 2-input 2-output automata with respect to an input permutation.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

A054748 Number of inequivalent n-state 1-input n-output automata.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A054742 Finite automata.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions