

A342234


a(n) = (27^n  9^n)/2  12^n + 6^n.


0



0, 3, 216, 7965, 243000, 6903873, 190505196, 5192233245, 140764942800, 3807455329593, 102881965757076, 2778771947174325, 75038262510065400, 2026169325431888913, 54708199287259567356, 1477140843778461200205, 39883035730488375376800, 1076844754605007952329833
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

For n >= 1, a(n) is the number of deterministic, completelydefined, initiallyconnected 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..M1} i^(f_i  f_{i1}  1)) * M^(M*N  f_{M1}  1), where the sum is taken over integers f_1, ..., f_{M1} satisfying 0 <= f_1 < N and f_{i1} < f_{i} < i*N for i = 2..M1. (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 (p1)!). It is Sum_{r=1..M} (1)^(r1) * 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)/(M1)! with N = n and M = 3. The sequence h_N(M) satisfies the recurrence h_N(M) = M^(N*M)  Sum_{t=1..M1} binomial(M1, t1) * M^(N*(Mt)) * h_N(t) with h_N(1) = 1. A recurrence for H_N(M) = h_N(M)/(M1)! originally appeared in Liskovets (1969, Eq. (3), p. 17, denoted by h_{n,r}).


LINKS

Table of n, a(n) for n=0..17.
M. Almeida, N. Moreira, and R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007), 93102; see B(k=3,n).
Valery A. Liskovets, The number of connected initial automata, Kibernetika (Kiev), 3 (1969), 1619 (in Russian; English translation: Cybernetics, 4 (1969), 259262).
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), 537551.
Robert W. Robinson, Counting strongly connected finite automata, pages 671685 in "Graph theory with applications to algorithms and computer science." Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 48, 1984. Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. LesniakFoster], D. R. Lick and C. E. Wall. A WileyInterscience 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, M1, binomial(M1, t1)*M^(N*(Mt))*h[N, t]))));
for(N=1, nn+1, H[N] = if(N==1, 0, h[N1, 3]/2)); H; }


CROSSREFS

Cf. A006689, A006690, A020522.
Sequence in context: A299395 A299225 A300037 * A225239 A225362 A063836
Adjacent sequences: A342231 A342232 A342233 * A342235 A342236 A342237


KEYWORD

nonn,easy


AUTHOR

Petros Hadjicostas, Mar 06 2021


STATUS

approved



