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

Author

Valery A. Liskovets, Apr 09 2003

Keywords

• easy
• nonn

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.

Crossrefs

Cf. A082159, A082158, A082172.

Programs

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

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

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

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.