A082170 - OEIS

%I #19 Jan 20 2024 09:27:21

%S 1,1,1,1,8,15,1,27,368,1024,1,64,2727,53672,198581,1,125,11904,710532,

%T 18417792,85102056,1,216,38375,4975936,386023509,12448430408,

%U 68999174203,1,343,101520,23945000,3977848832,381535651512,14734002979456,95264160938080

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

%C Array read by antidiagonals: (0,1),(0,2),(1,1),(0,3),...

%C The first column is A082158.

%H G. C. Greubel, <a href="/A082170/b082170.txt">Antidiagonals n = 0..50, flattened</a>

%H 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 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 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 The array begins:

%e             1,              1,               1,             1, ...;

%e             1,              8,              27,            64, ...;

%e            15,            368,            2727,         11904, ...;

%e          1024,          53672,          710532,       4975936, ...;

%e        198581,       18417792,       386023509,    3977848832, ...;

%e      85102056,    12448430408,    381535651512, 5451751738944, ...;

%e   68999174203, 14734002979456, 624245820664563, ...;

%e Antidiagonals begin as:

%e   1;

%e   1,   1;

%e   1,   8,    15;

%e   1,  27,   368,    1024;

%e   1,  64,  2727,   53672,    198581;

%e   1, 125, 11904,  710532,  18417792,    85102056;

%e   1, 216, 38375, 4975936, 386023509, 12448430408, 68999174203;

%t 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 Table[T[n-k-1, k], {n, 1, 9}, {k, n-1, 1, -1}]//Flatten (* _Jean-François Alcover_, Aug 29 2019 *)

%o (Magma)

%o function A(n,k)

%o   if n eq 0 then return 1;

%o   else return (&+[(-1)^(n-j+1)*Binomial(n,j)*(k+j)^(3*n-3*j)*A(j,k): j in [0..n-1]]);

%o   end if;

%o end function;

%o A082170:= func< n,k | A(k,n-k+1) >;

%o [A082170(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Jan 19 2024

%o (SageMath)

%o @CachedFunction

%o def A(n,k):

%o     if n==0: return 1

%o     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 def A082170(n,k): return A(k,n-k+1)

%o flatten([[A082170(n,k) for k in range(n+1)] for n in range(12)]) # _G. C. Greubel_, Jan 19 2024

%Y Cf. A082158, A082162, A082169.

%K easy,nonn,tabl

%O 0,5

%A _Valery A. Liskovets_, Apr 09 2003