The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A082163 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. 4
 1, 3, 15, 114, 1191, 15993, 263976, 5189778, 118729335, 3104549229, 91472523339, 3002047651764, 108699541743348, 4307549574285900, 185545521930558012, 8636223446937857130, 432133295481763698951, 23140414627731672497973, 1320835234697505382760757, 80076275471464881277266666, 5139849930933791535446756127 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS Coefficients T_2(n,k) form the array A082171. These automata have no nontrivial automorphisms (by states). 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 LINKS Valery A. Liskovets, The number of connected initial automata, 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.] 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. FORMULA 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".] 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 MATHEMATICA 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, n-1}]]]; Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Dec 15 2014, after PARI *) PROG (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 /* Second PARI program using Valery A. Liskovets's recurrence: */ 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 CROSSREFS Cf. A082159, A082161, A082171, A103236. Sequence in context: A123853 A335531 A166885 * A331122 A342167 A190629 Adjacent sequences:  A082160 A082161 A082162 * A082164 A082165 A082166 KEYWORD easy,nonn AUTHOR Valery A. Liskovets, Apr 09 2003 EXTENSIONS More terms from Petros Hadjicostas, Mar 06 2021 using the above programs STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 22 11:29 EDT 2021. Contains 345375 sequences. (Running on oeis4.)