A054050 - OEIS

%I #36 Dec 19 2021 12:06:25

%S 1,10,129,2836,83061,3076386,136647824,7081061404,419223006090,

%T 27914819962058,2064872379041701,167986348586006675,

%U 14906892578198245332,1432903480780688968334,148318150277923875087238,16447662583606982784243526,1945436946407977282783367806,244476687257496605058725664611

%N Number of nonisomorphic binary n-state automata.

%C Also, number of isomorphism classes of ordered pairs of endofunctions (i.e., an order pair (f,g) of functions) from {1,...,n} to itself. - _Christian G. Bower_, Dec 18 2003

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

%H M. A. Harrison, <a href="http://dx.doi.org/10.4153/CJM-1965-010-9">A census of finite automata</a>, Canad. J. Math., 17, No. 1, (1965), 100-113. [See p. 107 (Theorem 6.1 with k = 2 and p = 1) and p. 110 (Table I).]

%F 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} d*s_d)^(2*s_i). - _Christian G. Bower_, Dec 18 2003 [Corrected by _Petros Hadjicostas_, Mar 08 2021 using Theorem 6.1 in Harrison (1965) with k = 2 inputs and p = 1 output.]

%e From _Petros Hadjicostas_, Mar 08 2021: (Start)

%e For n = 2, we have the partitions 1*2 + 2*0 and 1*0 + 2*1 of 2 (in frequency notation). The corresponding denominators in _Christian G. Bower_'s formula are 1^2*2!*2^0*0! = 2 and 1^0*0!*2^1*1! = 2.

%e Also, fixA[s_1 = 2, s_2 = 0] = (Sum_{d|1} d*s_d)^(2*s_1) * (Sum_{d|2} d*s_d)^(2*s_2) = (1*s_1)^(2*s_1) = 16. In addition, fixA[s_1 = 0, s_2 = 1] = (Sum_{d|1} d*s_d)^(2*s_1) * (Sum_{d|2} d*s_d)^(2*s_2) = (1*s_1 + 2*s_2)^(2*s_2) = (0 + 2)^2 = 4. Hence a(2) = 16/2 + 4/2 = 10. (End)

%o (PARI) A054050(n)={local(p=vector(n));

%o my(S=0, A() = prod(i=1, n, sumdiv(i, d, d*p[d])^(2*p[i])),

%o 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

%Y Cf. A001372, A002854, A054745, A054051.

%K nonn

%O 1,2

%A _Vladeta Jovovic_, Apr 29 2000

%E a(16)-a(18) from _Petros Hadjicostas_, Mar 08 2021