login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 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.]
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
Sequence in context: A299395 A299225 A300037 * A225239 A225362 A063836
KEYWORD
nonn,easy
AUTHOR
Petros Hadjicostas, Mar 06 2021
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 00:26 EDT 2024. Contains 371264 sequences. (Running on oeis4.)