|
%I #19 Jan 20 2024 09:27:08
%S 1,1,1,1,4,7,1,9,56,142,1,16,207,1780,5941,1,25,544,9342,103392,
%T 428856,1,36,1175,32848,709893,9649124,47885899,1,49,2232,91150,
%U 3142528,82305144,1329514816,7685040448,1,64,3871,215892,10682325,440535696,13598786979,254821480596,1681740027657
%N Deterministic completely defined quasi-acyclic automata with 2 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 A082157.
%H G. C. Greubel, <a href="/A082169/b082169.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_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.
%e The array begins:
%e 1, 1, 1, 1, 1, ...;
%e 1, 4, 9, 16, 25, ...;
%e 7, 56, 207, 544, 1175, ...;
%e 142, 1780, 9342, 32848, 91150, ...;
%e 5941, 103392, 709893, 3142528, 10682325, ...;
%e 428856, 9649124, 82305144, 440535696, 1775027000, ...;
%e 47885899, 1329514816, 13598786979, 85529171200, ...;
%e Antidiagonal triangle begins as:
%e 1;
%e 1, 1;
%e 1, 4, 7;
%e 1, 9, 56, 142;
%e 1, 16, 207, 1780, 5941;
%e 1, 25, 544, 9342, 103392, 428856;
%e 1, 36, 1175, 32848, 709893, 9649124, 47885899;
%e 1, 49, 2232, 91150, 3142528, 82305144, 1329514816, 7685040448;
%t 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}];
%t Table[T[n-k-1, k], {n, 1, 10}, {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)^(2*n-2*j)*A(j,k): j in [0..n-1]]);
%o end if;
%o end function;
%o A082169:= func< n,k | A(k,n-k+1) >;
%o [A082169(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)^(2*n-2*j)*A(j,k) for j in range(n))
%o def A082169(n,k): return A(k,n-k+1)
%o flatten([[A082169(n,k) for k in range(n+1)] for n in range(12)]) # _G. C. Greubel_, Jan 19 2024
%Y Cf. A082157, A082161.
%K easy,nonn,tabl
%O 0,5
%A _Valery A. Liskovets_, Apr 09 2003
|
