cp's OEIS Frontend

A082159 Number of deterministic completely defined acyclic automata with 2 inputs and n+1 transient labeled states including a unique state having all transitions to the absorbing state.

%I A082159 #25 Jan 20 2024 09:26:40
%S A082159 1,3,39,1206,69189,6416568,881032059,168514815360,42934911510249,
%T A082159 14081311783382400,5786296490491543599,2914663547018935095552,
%U A082159 1767539279001227299807725,1271059349855055258673975296,1069996840045068513065229943875
%N A082159 Number of deterministic completely defined acyclic automata with 2 inputs and n+1 transient labeled states including a unique state having all transitions to the absorbing state.
%C A082159 This is the first column of the array A082171.
%H A082159 G. C. Greubel, <a href="/A082159/b082159.txt">Table of n, a(n) for n = 0..150</a>
%H A082159 Valery A. Liskovets, <a href="http://igm.univ-mlv.fr/~fpsac/FPSAC03/ARTICLES/5.pdf">Exact enumeration of acyclic automata</a>, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
%H A082159 Valery A. Liskovets, <a href="http://dx.doi.org/10.1016/j.dam.2005.06.009">Exact enumeration of acyclic deterministic automata</a>, Discrete Appl. Math., 154, No.3 (2006), 537-551.
%F A082159 a(n) = b_2(n), where b_2(0) = 1 and b_2(n) = Sum_{0..n-1} binomial(n, i) * (-1)^(n-i-1) * ((i + 2)^2 - 1)^(n-i) * b_2(i) for n > 0.
%t A082159 a[0] = 1; a[n_] := a[n] = Sum[Binomial[n, i] (-1)^(n - i - 1) ((i + 2)^2 - 1)^(n - i) a[i], {i, 0, n - 1}];
%t A082159 Table[a[n], {n, 0, 14}] (* _Jean-François Alcover_, Aug 29 2019 *)
%o A082159 (PARI) lista(nn)={my(a=vector(nn+1)); for(n=1, nn+1, a[n] = if(n==1, 1, sum(i=0, n-2, binomial(n-1, i)*(-1)^(n-i-2)*((i + 2)^2 - 1)^(n-i-1)*a[i+1]))); a;} \\ _Petros Hadjicostas_, Mar 07 2021
%o A082159 (Magma)
%o A082159 function a(n) // a = A082159
%o A082159   if n eq 0 then return 1;
%o A082159   else return (&+[Binomial(n,j)*(-1)^(n-j-1)*((j+2)^2 - 1)^(n-j)*a(j): j in [0..n-1]]);
%o A082159   end if;
%o A082159 end function;
%o A082159 [a(n): n in [0..20]]; // _G. C. Greubel_, Jan 17 2024
%o A082159 (SageMath)
%o A082159 @CachedFunction
%o A082159 def a(n): # A082159
%o A082159     if n==0: return 1
%o A082159     else: return sum(binomial(n,j)*(-1)^(n-j-1)*((j+2)^2 -1)^(n-j)*a(j) for j in range(n))
%o A082159 [a(n) for n in range(21)] # _G. C. Greubel_, Jan 17 2024
%Y A082159 Cf. A082157, A082160, A082171.
%K A082159 easy,nonn
%O A082159 0,2
%A A082159 _Valery A. Liskovets_, Apr 09 2003