|
|
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
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|