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

0, 3, 216, 7965, 243000, 6903873, 190505196, 5192233245, 140764942800, 3807455329593, 102881965757076, 2778771947174325, 75038262510065400, 2026169325431888913, 54708199287259567356, 1477140843778461200205, 39883035730488375376800, 1076844754605007952329833

Offset: 0

Author

Petros Hadjicostas, Mar 06 2021

Keywords

• nonn
• easy

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).

Crossrefs

Cf. A006689, A006690, A020522.

Programs

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;}

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