|
%I #39 Jan 20 2024 09:27:46
%S 1,1,3,1,8,39,1,15,176,1206,1,24,495,7784,69189,1,35,1104,29430,
%T 585408,6416568,1,48,2135,84600,2791125,67481928,881032059,1,63,3744,
%U 204470,9841728,389244600,11111547520,168514815360,1,80,6111,437616,28569765,1627740504,75325337235,2483829653544,42934911510249
%N A subclass of quasi-acyclic automata with 2 inputs, n transient and k absorbing labeled states; square array T(n,k) read by descending antidiagonals (n >= 0 and k >= 1).
%C Array read by descending antidiagonals: (0,1), (0,2), (1,1), (0,3), ...
%C The first column is A082159; i.e., T(n,k=1) = A082159(n). [The number n of transient states in the name of square array T(n,k) does not include the pre-dead transient state, which is, however, included in the name of A082159. See Section 3.1 in Liskovets (2006). - _Petros Hadjicostas_, Mar 07 2021]
%H G. C. Greubel, <a href="/A082171/b082171.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) = S_2(n, k) where S_2(0, k) := 1 and S_2(n, k) := Sum_{i=0..n-1} binomial(n, i)*(-1)^(n-i-1)*((i + k + 1)^2 - 1)^(n-i)*S_2(i, k) for n > 0.
%e Array T(n,k) (with rows n >= 0 and columns k >= 1) begins:
%e 1, 1, 1, 1, 1, ...;
%e 3, 8, 15, 24, 35, ...;
%e 39, 176, 495, 1104, 2135, ...;
%e 1206, 7784, 29430, 84600, 204470, ...;
%e 69189, 585408, 2791125, 9841728, 28569765, ...;
%e 6416568, 67481928, 389244600, 1627740504, ...;
%e 881032059, 11111547520, 75325337235, ...;
%e ...
%e Triangular array A(n,k) = T(k-1, n-k+1) (with rows n >= 1 and columns k = 1..n), read from the antidiagonals downwards of square array T:
%e 1;
%e 1, 3,
%e 1, 8, 39;
%e 1, 15, 176, 1206;
%e 1, 24, 495, 7784, 69189;
%e 1, 35, 1104, 29430, 585408, 6416568;
%e 1, 48, 2135, 84600, 2791125, 67481928, 881032059;
%e ...
%t T[0, _] = 1; T[n_, k_] := T[n, k] = Sum[Binomial[n, i] (-1)^(n - i - 1)*((i + k + 1)^2 - 1)^(n - i)*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 (PARI) lista(nn,kk)={my(T=matrix(nn+1,kk)); for(n=1, nn+1, for(k=1, kk, T[n,k] = if(n==1, 1, sum(i=0,n-2, binomial(n-1, i)*(-1)^(n-i-2)*((i + k + 1)^2 - 1)^(n-i-1)*T[i+1, k])))); T;} \\ _Petros Hadjicostas_, Mar 07 2021
%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+1)^2-1)^(n-j)*A(j,k): j in [0..n-1]]);
%o end if;
%o end function;
%o A082171:= func< n,k | A(k,n-k+1) >;
%o [A082171(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+1)^2-1)^(n-j)*A(j,k) for j in range(n))
%o def A082171(n,k): return A(k,n-k+1)
%o flatten([[A082171(n,k) for k in range(n+1)] for n in range(12)]) # _G. C. Greubel_, Jan 19 2024
%Y Cf. A082159, A082163, A082169.
%K easy,nonn,tabl
%O 0,3
%A _Valery A. Liskovets_, Apr 09 2003
%E Name clarified by _Petros Hadjicostas_, Mar 07 2021
|
