cp's OEIS Frontend

A082170 Deterministic completely defined quasi-acyclic automata with 3 inputs, n transient and k absorbing labeled states.

%I A082170 #19 Jan 20 2024 09:27:21
%S A082170 1,1,1,1,8,15,1,27,368,1024,1,64,2727,53672,198581,1,125,11904,710532,
%T A082170 18417792,85102056,1,216,38375,4975936,386023509,12448430408,
%U A082170 68999174203,1,343,101520,23945000,3977848832,381535651512,14734002979456,95264160938080
%N A082170 Deterministic completely defined quasi-acyclic automata with 3 inputs, n transient and k absorbing labeled states.
%C A082170 Array read by antidiagonals: (0,1),(0,2),(1,1),(0,3),...
%C A082170 The first column is A082158.
%H A082170 G. C. Greubel, <a href="/A082170/b082170.txt">Antidiagonals n = 0..50, flattened</a>
%H A082170 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 A082170 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 A082170 T(n, k) = T_3(n, k) where T_3(0, k) = 1, T_3(n, k) = Sum_{i=0..n-1} (-1)^(n-i-1)*binomial(n, i)*(i+k)^(3*n-3*i)*T_3(i, k), n > 0.
%e A082170 The array begins:
%e A082170             1,              1,               1,             1, ...;
%e A082170             1,              8,              27,            64, ...;
%e A082170            15,            368,            2727,         11904, ...;
%e A082170          1024,          53672,          710532,       4975936, ...;
%e A082170        198581,       18417792,       386023509,    3977848832, ...;
%e A082170      85102056,    12448430408,    381535651512, 5451751738944, ...;
%e A082170   68999174203, 14734002979456, 624245820664563, ...;
%e A082170 Antidiagonals begin as:
%e A082170   1;
%e A082170   1,   1;
%e A082170   1,   8,    15;
%e A082170   1,  27,   368,    1024;
%e A082170   1,  64,  2727,   53672,    198581;
%e A082170   1, 125, 11904,  710532,  18417792,    85102056;
%e A082170   1, 216, 38375, 4975936, 386023509, 12448430408, 68999174203;
%t A082170 T[0, _] = 1; T[n_, k_]:= T[n, k] = Sum[Binomial[n, i] (-1)^(n-i-1)*(i + k)^(3n-3i) T[i, k], {i,0,n-1}];
%t A082170 Table[T[n-k-1, k], {n, 1, 9}, {k, n-1, 1, -1}]//Flatten (* _Jean-François Alcover_, Aug 29 2019 *)
%o A082170 (Magma)
%o A082170 function A(n,k)
%o A082170   if n eq 0 then return 1;
%o A082170   else return (&+[(-1)^(n-j+1)*Binomial(n,j)*(k+j)^(3*n-3*j)*A(j,k): j in [0..n-1]]);
%o A082170   end if;
%o A082170 end function;
%o A082170 A082170:= func< n,k | A(k,n-k+1) >;
%o A082170 [A082170(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Jan 19 2024
%o A082170 (SageMath)
%o A082170 @CachedFunction
%o A082170 def A(n,k):
%o A082170     if n==0: return 1
%o A082170     else: return sum((-1)^(n-j+1)*binomial(n,j)*(k+j)^(3*n-3*j)*A(j,k) for j in range(n))
%o A082170 def A082170(n,k): return A(k,n-k+1)
%o A082170 flatten([[A082170(n,k) for k in range(n+1)] for n in range(12)]) # _G. C. Greubel_, Jan 19 2024
%Y A082170 Cf. A082158, A082162, A082169.
%K A082170 easy,nonn,tabl
%O A082170 0,5
%A A082170 _Valery A. Liskovets_, Apr 09 2003