OFFSET
0,2
COMMENTS
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.
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.
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.)
Both formulas with N = n and M = 3 give a(n) = (27^n - 9^n)/2 - 12^n + 6^n.
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}).
LINKS
M. Almeida, N. Moreira, and R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007), 93-102; see B(k=3,n).
Valery A. Liskovets, The number of connected initial automata, Kibernetika (Kiev), 3 (1969), 16-19 (in Russian; English translation: Cybernetics, 4 (1969), 259-262).
Valery A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
Valery A. Liskovets, Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, No. 3 (2006), 537-551.
Robert W. Robinson, Counting strongly connected finite automata, 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.]
Index entries for linear recurrences with constant coefficients, signature (54,-963,6966,-17496).
FORMULA
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
PROG
(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]))));
for(N=1, nn+1, H[N] = if(N==1, 0, h[N-1, 3]/2)); H; }
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Petros Hadjicostas, Mar 06 2021
STATUS
approved