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

Author

Valery A. Liskovets, Apr 09 2003

Keywords

• easy
• nonn
• tabl

Comments

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

The first column is A082157.

Examples

			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;
		

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.

Crossrefs

Cf. A082157, A082161.

Programs

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

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 *)

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

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.