login
A082170
Deterministic completely defined quasi-acyclic automata with 3 inputs, n transient and k absorbing labeled states.
5
1, 1, 1, 1, 8, 15, 1, 27, 368, 1024, 1, 64, 2727, 53672, 198581, 1, 125, 11904, 710532, 18417792, 85102056, 1, 216, 38375, 4975936, 386023509, 12448430408, 68999174203, 1, 343, 101520, 23945000, 3977848832, 381535651512, 14734002979456, 95264160938080
OFFSET
0,5
COMMENTS
Array read by antidiagonals: (0,1),(0,2),(1,1),(0,3),...
The first column is A082158.
LINKS
Valery A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
Valery A. Liskovets, Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, No.3 (2006), 537-551.
FORMULA
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.
EXAMPLE
The array begins:
1, 1, 1, 1, ...;
1, 8, 27, 64, ...;
15, 368, 2727, 11904, ...;
1024, 53672, 710532, 4975936, ...;
198581, 18417792, 386023509, 3977848832, ...;
85102056, 12448430408, 381535651512, 5451751738944, ...;
68999174203, 14734002979456, 624245820664563, ...;
Antidiagonals begin as:
1;
1, 1;
1, 8, 15;
1, 27, 368, 1024;
1, 64, 2727, 53672, 198581;
1, 125, 11904, 710532, 18417792, 85102056;
1, 216, 38375, 4975936, 386023509, 12448430408, 68999174203;
MATHEMATICA
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}];
Table[T[n-k-1, k], {n, 1, 9}, {k, n-1, 1, -1}]//Flatten (* Jean-François Alcover, Aug 29 2019 *)
PROG
(Magma)
function A(n, k)
if n eq 0 then return 1;
else return (&+[(-1)^(n-j+1)*Binomial(n, j)*(k+j)^(3*n-3*j)*A(j, k): j in [0..n-1]]);
end if;
end function;
A082170:= func< n, k | A(k, n-k+1) >;
[A082170(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jan 19 2024
(SageMath)
@CachedFunction
def A(n, k):
if n==0: return 1
else: return sum((-1)^(n-j+1)*binomial(n, j)*(k+j)^(3*n-3*j)*A(j, k) for j in range(n))
def A082170(n, k): return A(k, n-k+1)
flatten([[A082170(n, k) for k in range(n+1)] for n in range(12)]) # G. C. Greubel, Jan 19 2024
CROSSREFS
KEYWORD
easy,nonn,tabl
AUTHOR
Valery A. Liskovets, Apr 09 2003
STATUS
approved