|
%I #27 Jan 20 2024 09:26:29
%S 1,1,15,1024,198581,85102056,68999174203,95264160938080,
%T 207601975572545961,674354204416939196800,3122476748685067008205511,
%U 19884561572783089348189507584,169123749545536919971662851459485,1874777145334671354828947023095675904,26531967154935836079418311035871122812275
%N Number of deterministic completely defined acyclic automata with 3 inputs and n transient labeled states (and a unique absorbing state).
%C This is the first column of the array A082170.
%H G. C. Greubel, <a href="/A082158/b082158.txt">Table of n, a(n) for n = 0..150</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 a(n) = a_3(n) where a_3(0) = 1, a_3(n) = Sum_{i=0..n-1} binomial(n, i)*(-1)^(n-i-1)*(i+1)^(3*n-3*i)*a_3(i), n > 0.
%F 1 = Sum_{n>=0} a(n)*exp(-(1+n)^3*x)*x^n/n!. - _Vladeta Jovovic_, Jul 18 2005
%F From _Paul D. Hanna_, May 03 2015: (Start)
%F 1 = Sum_{n>=0} a(n) * x^n/(1 + (n+1)^3*x)^(n+1).
%F 1 = Sum_{n>=0} a(n) * C(n+m-1,n) * x^n/(1 + (n+1)^3*x)^(n+m) for all m>=1.
%F log(1+x) = Sum_{n>=1} a(n) * x^n/(1 + (n+1)^3*x)^n/n. (End)
%t a[n_] := If[n == 0, 1, Sum[-(-1)^(n-k) Binomial[n, k] (k+1)^(3(n-k)) a[k], {k, 0, n-1}]];
%t Table[a[n], {n, 0, 11}] (* _Jean-François Alcover_, Aug 29 2019 *)
%o (PARI) {a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+(k+1)^3*x+x*O(x^n))^(k+1)), n)}
%o for(n=0,20,print1(a(n),", ")) \\ _Paul D. Hanna_, May 03 2015
%o (PARI) {a(n)=if(n==0, 1, sum(k=0, n-1, -(-1)^(n-k)*binomial(n, k)*(k+1)^(3*(n-k))*a(k)))}
%o for(n=0,20,print1(a(n),", ")) \\ _Paul D. Hanna_, May 03 2015
%o (Magma)
%o function a(n) // a = A082158
%o if n eq 0 then return 1;
%o else return (&+[Binomial(n,j)*(-1)^(n-j-1)*(j+1)^(3*n-3*j)*a(j): j in [0..n-1]]);
%o end if;
%o end function;
%o [a(n): n in [0..20]]; // _G. C. Greubel_, Jan 17 2024
%o (SageMath)
%o @CachedFunction
%o def a(n): # A082158
%o if n==0: return 1
%o else: return sum(binomial(n,j)*(-1)^(n-j-1)*(j+1)^(3*n-3*j)*a(j) for j in range(n))
%o [a(n) for n in range(21)] # _G. C. Greubel_, Jan 17 2024
%Y Cf. A082157, A082159, A082160, A082170.
%K easy,nonn
%O 0,3
%A _Valery A. Liskovets_, Apr 09 2003
%E More terms from _Michel Marcus_, Aug 29 2019
| 