A082158 Number of deterministic completely defined acyclic automata with 3 inputs and n transient labeled states (and a unique absorbing state).

1, 1, 15, 1024, 198581, 85102056, 68999174203, 95264160938080, 207601975572545961, 674354204416939196800, 3122476748685067008205511, 19884561572783089348189507584, 169123749545536919971662851459485, 1874777145334671354828947023095675904, 26531967154935836079418311035871122812275

Offset

0,3

Comments

This is the first column of the array A082170.

Links

G. C. Greubel, Table of n, a(n) for n = 0..150

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.

Formula

a(n) = a_3(n) where a_3(0) = 1, a_3(n) = Sum_{i=0..n-1} binomial(n, i)*(-1)^(n-i-1)*(i+1)^(3*n-3*i)*a_3(i), n > 0.

1 = Sum_{n>=0} a(n)*exp(-(1+n)^3*x)*x^n/n!. - Vladeta Jovovic, Jul 18 2005

From Paul D. Hanna, May 03 2015: (Start)

1 = Sum_{n>=0} a(n) * x^n/(1 + (n+1)^3*x)^(n+1).

1 = Sum_{n>=0} a(n) * C(n+m-1,n) * x^n/(1 + (n+1)^3*x)^(n+m) for all m>=1.

log(1+x) = Sum_{n>=1} a(n) * x^n/(1 + (n+1)^3*x)^n/n. (End)

Mathematica

a[n_] := If[n == 0, 1, Sum[-(-1)^(n-k) Binomial[n, k] (k+1)^(3(n-k)) a[k], {k, 0, n-1}]];
Table[a[n], {n, 0, 11}] (* Jean-François Alcover, Aug 29 2019 *)

Prog

(PARI) {a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+(k+1)^3*x+x*O(x^n))^(k+1)), n)}
for(n=0, 20, print1(a(n), ", ")) \\ Paul D. Hanna, May 03 2015
(PARI) {a(n)=if(n==0, 1, sum(k=0, n-1, -(-1)^(n-k)*binomial(n, k)*(k+1)^(3*(n-k))*a(k)))}
for(n=0, 20, print1(a(n), ", ")) \\ Paul D. Hanna, May 03 2015
(Magma)
function a(n) // a = A082158
  if n eq 0 then return 1;
  else return (&+[Binomial(n, j)*(-1)^(n-j-1)*(j+1)^(3*n-3*j)*a(j): j in [0..n-1]]);
  end if;
end function;
[a(n): n in [0..20]]; // G. C. Greubel, Jan 17 2024
(SageMath)
@CachedFunction
def a(n): # A082158
    if n==0: return 1
    else: return sum(binomial(n, j)*(-1)^(n-j-1)*(j+1)^(3*n-3*j)*a(j) for j in range(n))
[a(n) for n in range(21)] # G. C. Greubel, Jan 17 2024

Crossrefs

Cf. A082157, A082159, A082160, A082170.

Sequence in context: A102102 A196569 A019282 * A064625 A241331 A205602

Adjacent sequences: A082155 A082156 A082157 * A082159 A082160 A082161

Keyword

easy,nonn

Author

Valery A. Liskovets, Apr 09 2003

Extensions

More terms from Michel Marcus, Aug 29 2019

Status

approved