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

 

Logo


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 (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

REFERENCES

V. A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.

LINKS

Table of n, a(n) for n=1..15.

V. A. Liskovets, Exact enumeration of acyclic deterministic automata,Discrete Appl. Math., 154, No.3 (2006), 537-551.

FORMULA

a(n) := d_2(n)/(n-1)! where d_2(n) := T_2(n, 1)-sum(binomial(n-1, j-1)*T_2(n-j, j+1)*d_2(j), j=1..n-1); and T_2(0, k) := 1, T_2(n, k) := sum(binomial(n, i)*(-1)^(n-i-1)*((i+k+1)^2-1)^(n-i)*T_2(i, k), i=0..n-1), n>0.

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)))} (Hanna)

CROSSREFS

Cf. A082159, A082161.

Cf. A103236.

Sequence in context: A059849 A123853 A166885 * A331122 A190629 A074596

Adjacent sequences:  A082160 A082161 A082162 * A082164 A082165 A082166

KEYWORD

easy,nonn

AUTHOR

Valery A. Liskovets, Apr 09 2003

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 26 23:05 EST 2020. Contains 331289 sequences. (Running on oeis4.)