cp's OEIS Frontend

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

%I A082169 #19 Jan 20 2024 09:27:08
%S A082169 1,1,1,1,4,7,1,9,56,142,1,16,207,1780,5941,1,25,544,9342,103392,
%T A082169 428856,1,36,1175,32848,709893,9649124,47885899,1,49,2232,91150,
%U A082169 3142528,82305144,1329514816,7685040448,1,64,3871,215892,10682325,440535696,13598786979,254821480596,1681740027657
%N A082169 Deterministic completely defined quasi-acyclic automata with 2 inputs, n transient and k absorbing labeled states.
%C A082169 Array read by antidiagonals: (0,1),(0,2),(1,1),(0,3),...
%C A082169 The first column is A082157.
%H A082169 G. C. Greubel, <a href="/A082169/b082169.txt">Antidiagonals n = 0..50, flattened</a>
%H A082169 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 A082169 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 A082169 T(n, k) = T_2(n, k) where T_2(0, k) = 1, T_2(n, k) = Sum_{i=0..n-1} (-1)^(n-i-1)*binomial(n, i)*(i+k)^(2*(n-i))*T_2(i, k), n > 0.
%e A082169 The array begins:
%e A082169          1,          1,           1,           1,          1, ...;
%e A082169          1,          4,           9,          16,         25, ...;
%e A082169          7,         56,         207,         544,       1175, ...;
%e A082169        142,       1780,        9342,       32848,      91150, ...;
%e A082169       5941,     103392,      709893,     3142528,   10682325, ...;
%e A082169     428856,    9649124,    82305144,   440535696, 1775027000, ...;
%e A082169   47885899, 1329514816, 13598786979, 85529171200, ...;
%e A082169 Antidiagonal triangle begins as:
%e A082169   1;
%e A082169   1,  1;
%e A082169   1,  4,    7;
%e A082169   1,  9,   56,   142;
%e A082169   1, 16,  207,  1780,    5941;
%e A082169   1, 25,  544,  9342,  103392,   428856;
%e A082169   1, 36, 1175, 32848,  709893,  9649124,   47885899;
%e A082169   1, 49, 2232, 91150, 3142528, 82305144, 1329514816, 7685040448;
%t A082169 T[0, _]= 1; T[n_, k_]:= T[n, k]= Sum[Binomial[n, i] (-1)^(n-i-1)*(i + k)^(2n-2i) T[i, k], {i, 0, n-1}];
%t A082169 Table[T[n-k-1, k], {n, 1, 10}, {k, n-1, 1, -1}]//Flatten (* _Jean-François Alcover_, Aug 29 2019 *)
%o A082169 (Magma)
%o A082169 function A(n,k)
%o A082169   if n eq 0 then return 1;
%o A082169   else return (&+[(-1)^(n-j+1)*Binomial(n,j)*(k+j)^(2*n-2*j)*A(j,k): j in [0..n-1]]);
%o A082169   end if;
%o A082169 end function;
%o A082169 A082169:= func< n,k | A(k,n-k+1) >;
%o A082169 [A082169(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Jan 19 2024
%o A082169 (SageMath)
%o A082169 @CachedFunction
%o A082169 def A(n,k):
%o A082169     if n==0: return 1
%o A082169     else: return sum((-1)^(n-j+1)*binomial(n,j)*(k+j)^(2*n-2*j)*A(j,k) for j in range(n))
%o A082169 def A082169(n,k): return A(k,n-k+1)
%o A082169 flatten([[A082169(n,k) for k in range(n+1)] for n in range(12)]) # _G. C. Greubel_, Jan 19 2024
%Y A082169 Cf. A082157, A082161.
%K A082169 easy,nonn,tabl
%O A082169 0,5
%A A082169 _Valery A. Liskovets_, Apr 09 2003