A082160 Deterministic completely defined acyclic automata with 3 inputs and n+1 transient labeled states including a unique state having all transitions to the absorbing state.

1, 7, 315, 45682, 15646589, 10567689552, 12503979423607, 23841011541867520, 68835375121428936153, 286850872894190847235840, 1660638682341609286358474579, 12947089879912710544534553836032

Offset

0,2

Comments

This is the first column of the array A082172.

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) = b_3(n) where b_3(0) = 1, b_3(n) = Sum_{i=0..n-1} binomial(n, i)*(-1)^(n-i-1)*((i+2)^3 - 1)^(n-i)*b_3(i), n > 0.

Mathematica

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

Prog

(Magma)
function a(n) // a = A082160
  if n eq 0 then return 1;
  else return (&+[Binomial(n, j)*(-1)^(n-j-1)*((j+2)^3 - 1)^(n-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): # A082160
    if n==0: return 1
    else: return sum(binomial(n, j)*(-1)^(n-j-1)*((j+2)^3 -1)^(n-j)*a(j) for j in range(n))
[a(n) for n in range(21)] # G. C. Greubel, Jan 17 2024

Crossrefs

Cf. A082159, A082158, A082172.

Sequence in context: A171148 A219267 A244851 * A220278 A163437 A109059

Adjacent sequences: A082157 A082158 A082159 * A082161 A082162 A082163

Keyword

easy,nonn

Author

Valery A. Liskovets, Apr 09 2003

Status

approved