cp's OEIS Frontend

A082172 A subclass of quasi-acyclic automata with 3 inputs, n transient and k absorbing labeled states.

%I A082172 #20 Jan 19 2024 04:31:42
%S A082172 1,1,7,1,26,315,1,63,2600,45682,1,124,11655,675194,15646589,1,215,
%T A082172 37944,4861458,366349152,10567689552,1,342,100835,23641468,3882676581,
%U A082172 361884843866,12503979423607,1,511,232560,89076650,26387681120,5318920238688,591934698991168,23841011541867520
%N A082172 A subclass of quasi-acyclic automata with 3 inputs, n transient and k absorbing labeled states.
%C A082172 Array read by antidiagonals: (0,1),(0,2),(1,1),(0,3),... . The first column is A082160.
%H A082172 G. C. Greubel, <a href="/A082172/b082172.txt">Antidiagonals n = 0..50, flattened</a>
%H A082172 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 A082172 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 A082172 T(n, k) = S_3(n, k) where S_3(0, k) = 1, S_3(n, k) = Sum_{i=0..n-1} (-1)^(n-i-1)*binomial(n, i)*((i+k+1)^3-1)^(n-i)*S_3(i, k), n > 0.
%e A082172 The array begins:
%e A082172                1,            1,          1,           1,        1, ...;
%e A082172                7,           26,         63,         124,      215, ...;
%e A082172              315,         2600,      11655,       37944,   100835, ...;
%e A082172            45682,       675194,    4861458,    23641468, 89076650, ...;
%e A082172         15646589,    366349152, 3882676581, 26387681120, ...;
%e A082172      10567689552, 361884843866, ...;
%e A082172   12503979423607,  ...;
%e A082172 Antidiagonals begin as:
%e A082172   1;
%e A082172   1,   7;
%e A082172   1,  26,    315;
%e A082172   1,  63,   2600,    45682;
%e A082172   1, 124,  11655,   675194,   15646589;
%e A082172   1, 215,  37944,  4861458,  366349152,  10567689552;
%e A082172   1, 342, 100835, 23641468, 3882676581, 361884843866, 12503979423607;
%t A082172 T[0, _] = 1; T[n_, k_] := T[n, k] = Sum[Binomial[n, i]*(-1)^(n - i - 1)*((i + k + 1)^3 - 1)^(n - i)*T[i, k], {i, 0, n - 1}];
%t A082172 Table[T[n-k, k], {n, 1, 9}, {k, n, 1, -1}]//Flatten (* _Jean-François Alcover_, Aug 27 2019 *)
%o A082172 (Magma)
%o A082172 function A(n,k)
%o A082172   if n eq 0 then return 1;
%o A082172   else return (&+[(-1)^(n-j+1)*Binomial(n,j)*((k+j+1)^3-1)^(n-j)*A(j,k): j in [0..n-1]]);
%o A082172   end if;
%o A082172 end function;
%o A082172 A082172:= func< n,k | A(k,n-k+1) >;
%o A082172 [A082172(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Jan 19 2024
%o A082172 (SageMath)
%o A082172 @CachedFunction
%o A082172 def A(n,k):
%o A082172     if n==0: return 1
%o A082172     else: return sum((-1)^(n-j+1)*binomial(n,j)*((k+j+1)^3-1)^(n-j)*A(j,k) for j in range(n))
%o A082172 def A082172(n,k): return A(k,n-k+1)
%o A082172 flatten([[A082172(n,k) for k in range(n+1)] for n in range(12)]) # _G. C. Greubel_, Jan 19 2024
%Y A082172 Cf. A082160, A082164, A082170, A082171.
%K A082172 easy,nonn,tabl
%O A082172 0,3
%A A082172 _Valery A. Liskovets_, Apr 09 2003