%I #35 Mar 08 2021 22:51:41
%S 0,3,216,7965,243000,6903873,190505196,5192233245,140764942800,
%T 3807455329593,102881965757076,2778771947174325,75038262510065400,
%U 2026169325431888913,54708199287259567356,1477140843778461200205,39883035730488375376800,1076844754605007952329833
%N a(n) = (27^n - 9^n)/2 - 12^n + 6^n.
%C For n >= 1, a(n) is the number of deterministic, completely-defined, initially-connected finite automata with n inputs and 3 unlabeled states. A020522 counts similar automata with n inputs and 2 unlabeled states.
%C According to a comment by _Nelma Moreira_ in A006689 and A006690, the number of such automata with N inputs and M unlabeled states is Sum (Product_{i=1..M-1} i^(f_i - f_{i-1} - 1)) * M^(M*N - f_{M-1} - 1), where the sum is taken over integers f_1, ..., f_{M-1} satisfying 0 <= f_1 < N and f_{i-1} < f_{i} < i*N for i = 2..M-1. (See Theorem 8 in Almeida, Moreira, and Reis (2007). The value of f_0 is not relevant.) For this sequence we have M = 3 unlabeled states, for A020522 we have M = 2 unlabeled states, for A006689 we have N = 2 inputs, and for A006690 we have N = 3 inputs.
%C A similar formula for the number of such automata with N inputs and M unlabeled states was given by Robinson (1985, Eq. (2.3) upon division by (p-1)!). It is Sum_{r=1..M} (-1)^(r-1) * Sum_{k_1,...,k_r} (k_1/(Product_{i=1..r} k_i!)) * Product_{j=1..r} (Sum_{i=1..j} k_i)^(N*k_j), where the second sum is over all compositions (k_1,...,k_r) of length r of M. (A composition of length r of M is an ordered partition (k_1,...,k_r) with k_i >= 1 for i = 1..r and Sum_{i=1..r} k_i = M.)
%C Both formulas with N = n and M = 3 give a(n) = (27^n - 9^n)/2 - 12^n + 6^n.
%C In Liskovets (2006, Eq. (11), p. 546), a(n) equals H_N(M) = h_N(M)/(M-1)! with N = n and M = 3. The sequence h_N(M) satisfies the recurrence h_N(M) = M^(N*M) - Sum_{t=1..M-1} binomial(M-1, t-1) * M^(N*(M-t)) * h_N(t) with h_N(1) = 1. A recurrence for H_N(M) = h_N(M)/(M-1)! originally appeared in Liskovets (1969, Eq. (3), p. 17, denoted by h_{n,r}).
%H M. Almeida, N. Moreira, and R. Reis, <a href="http://dx.doi.org/10.1016/j.tcs.2007.07.029">Enumeration and generation with a string automata representation</a>, Theor. Comp. Sci. 387 (2007), 93-102; see B(k=3,n).
%H Valery A. Liskovets, <a href="https://www.researchgate.net/publication/245012762_The_number_of_connected_initial_automata">The number of connected initial automata</a>, Kibernetika (Kiev), 3 (1969), 16-19 (in Russian; English translation: Cybernetics, 4 (1969), 259-262).
%H Valery A. Liskovets, <a href="http://igm.univ-mlv.fr/~fpsac/FPSAC03/ARTICLES/5.pdf">Exact enumeration of acyclic automata</a>, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
%H Valery A. Liskovets, <a href="http://dx.doi.org/10.1016/j.dam.2005.06.009">Exact enumeration of acyclic deterministic automata</a>, Discrete Appl. Math., 154, No. 3 (2006), 537-551.
%H Robert W. Robinson, <a href="/A006689/a006689_1.pdf">Counting strongly connected finite automata</a>, pages 671-685 in "Graph theory with applications to algorithms and computer science." Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4-8, 1984. Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. Wall. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1985. [Annotated scanned copy, with permission of the author.]
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (54,-963,6966,-17496).
%F G.f.: 3*x*(1 + 18*x - 270*x^2)/(1 - 54*x + 963*x^2 - 6966*x^3 + 17496*x^4). - _Stefano Spezia_, Mar 08 2021
%o (PARI) lista(nn) = {my(h=matrix(nn+3,nn+3)); my(H=vector(nn+1)); for(N=1, nn, for(M=1, nn, h[N,M] = if(M==1, 1, M^(N*M)-sum(t=1,M-1, binomial(M-1, t-1)*M^(N*(M-t))*h[N,t]))));
%o for(N=1, nn+1, H[N] = if(N==1, 0, h[N-1,3]/2)); H;}
%Y Cf. A006689, A006690, A020522.
%K nonn,easy
%O 0,2
%A _Petros Hadjicostas_, Mar 06 2021