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

1, 1, 1, 1, 4, 7, 1, 9, 56, 142, 1, 16, 207, 1780, 5941, 1, 25, 544, 9342, 103392, 428856, 1, 36, 1175, 32848, 709893, 9649124, 47885899, 1, 49, 2232, 91150, 3142528, 82305144, 1329514816, 7685040448, 1, 64, 3871, 215892, 10682325, 440535696, 13598786979, 254821480596, 1681740027657

Offset

0,5

Comments

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

The first column is A082157.

Links

G. C. Greubel, Antidiagonals n = 0..50, flattened

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_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.

Example

The array begins:
         1,          1,           1,           1,          1, ...;
         1,          4,           9,          16,         25, ...;
         7,         56,         207,         544,       1175, ...;
       142,       1780,        9342,       32848,      91150, ...;
      5941,     103392,      709893,     3142528,   10682325, ...;
    428856,    9649124,    82305144,   440535696, 1775027000, ...;
  47885899, 1329514816, 13598786979, 85529171200, ...;
Antidiagonal triangle begins as:
  1;
  1,  1;
  1,  4,    7;
  1,  9,   56,   142;
  1, 16,  207,  1780,    5941;
  1, 25,  544,  9342,  103392,   428856;
  1, 36, 1175, 32848,  709893,  9649124,   47885899;
  1, 49, 2232, 91150, 3142528, 82305144, 1329514816, 7685040448;

Mathematica

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}];
Table[T[n-k-1, k], {n, 1, 10}, {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)^(2*n-2*j)*A(j, k): j in [0..n-1]]);
  end if;
end function;
A082169:= func< n, k | A(k, n-k+1) >;
[A082169(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)^(2*n-2*j)*A(j, k) for j in range(n))
def A082169(n, k): return A(k, n-k+1)
flatten([[A082169(n, k) for k in range(n+1)] for n in range(12)]) # G. C. Greubel, Jan 19 2024

Crossrefs

Cf. A082157, A082161.

Sequence in context: A019670 A093436 A343805 * A209634 A340584 A289523

Adjacent sequences: A082166 A082167 A082168 * A082170 A082171 A082172

Keyword

easy,nonn,tabl

Author

Valery A. Liskovets, Apr 09 2003

Status

approved