|
%I #40 Mar 08 2021 02:10:50
%S 1,3,15,114,1191,15993,263976,5189778,118729335,3104549229,
%T 91472523339,3002047651764,108699541743348,4307549574285900,
%U 185545521930558012,8636223446937857130,432133295481763698951,23140414627731672497973,1320835234697505382760757,80076275471464881277266666,5139849930933791535446756127
%N Number of deterministic completely defined initially connected acyclic automata with 2 inputs and n+1 transient unlabeled states including a unique state having all transitions to the absorbing state.
%C Coefficients T_2(n,k) form the array A082171. These automata have no nontrivial automorphisms (by states).
%C Also equals the leftmost column of triangular matrix M=A103236, which satisfies: M^2 + 2*M = SHIFTUP(M) (i.e. each column of M shifts up 1 row). - _Paul D. Hanna_, Jan 29 2005
%H Valery A. Liskovets, <a href="https://www.researchgate.net/publication/245012762_The_number_of_connected_initial_automata">The number of connected initial automata</a>, Kibernetika (Kiev), 3 (1969), 16-19 (in Russian; English translation: Cybernetics, 4 (1969), 259-262). [It includes the original methodology that he used in his 2003 and 2006 papers.]
%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(1) = 1 and a(n) := d_2(n-1)/(n-2)! for n >= 2, where d_2(n) := T_2(n, 1) - Sum_{j=1..n-1} binomial(n-1, j-1) * T_2(n-j, j+1) * d_2(j); and T_2(0, k) := 1, T_2(n, k) := Sum_{i=0..n-1} binomial(n, i) * (-1)^(n-i-1) *((i+k+1)^2 - 1)^(n-i) * T_2(i, k) for n > 0. [Edited by _Petros Hadjicostas_, Mar 06 2021 to agree with Theorem 3.3 (p. 543) in Liskovets (2006). Here, n + 1 is "the number of transient states including the pre-dead state".]
%F G.f.: 1 = Sum_{n>=0} a(n+1) * (x^n/(1-2*x)^n) * Product_{k=0..n} (1 - (3 + k)*x). Thus: 1 = 1*(1-3x) + 3*(x/(1-2x))*(1-3x)*(1-4x) + 15*(x^2/(1-2x)^2)*(1-3x)*(1-4x)*(1-5x) + 114*(x^3/(1-2x)^3)*(1-3x)*(1-4x)*(1-5x)*(1-6x) + ... - _Paul D. Hanna_, Jan 29 2005
%t a[n_] := a[n] = If[n<1, 0, If[n == 1, 1, SeriesCoefficient[1-Sum[a[k+1]*x^k/(1-2*x)^k*Product[1-(j+3)*x, {j, 0, k}], {k, 0, n-2}], {x, 0,
%t n-1}]]]; Table[a[n], {n, 1, 15}] (* _Jean-François Alcover_, Dec 15 2014, after PARI *)
%o (PARI) {a(n)=if(n<1,0,if(n==1,1,polcoeff( 1-sum(k=0,n-2,a(k+1)*x^k/(1-2*x)^k*prod(j=0,k,1-(j+3)*x+x*O(x^n))),n-1)))} \\ _Paul D. Hanna_, Jan 29 2005
%o /* Second PARI program using _Valery A. Liskovets_'s recurrence: */
%o lista(nn)={my(T=matrix(nn+1, nn+1)); my(d=vector(nn)); my(a=vector(nn)); for(n=1, nn+1, for(k=1, nn, 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])))); for(n=1, nn, d[n] = T[n+1,1] - sum(j=1, n-1, binomial(n-1, j-1)*T[n-j+1, j+1]*d[j])); for(n=1, nn, a[n] = if(n==1, 1, d[n-1]/(n-2)!)); a;} \\ _Petros Hadjicostas_, Mar 07 2021
%Y Cf. A082159, A082161, A082171, A103236.
%K easy,nonn
%O 1,2
%A _Valery A. Liskovets_, Apr 09 2003
%E More terms from _Petros Hadjicostas_, Mar 06 2021 using the above programs
|
