The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A082161 Number of deterministic completely defined initially connected acyclic automata with 2 inputs and n transient unlabeled states (and a unique absorbing state). 22
1, 3, 16, 127, 1363, 18628, 311250, 6173791, 142190703, 3737431895, 110577492346, 3641313700916, 132214630355700, 5251687490704524, 226664506308709858, 10568175957745041423, 529589006347242691143, 28395998790096299447521 (list; graph; refs; listen; history; text; internal format)



Coefficients T_2(n,k) form the array A082169. These automata have no nontrivial automorphisms (by states).

Also counts the relaxed compacted binary trees of size n. A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. See the Genitrini et al. link. - Michael Wallner, Apr 20 2017


R. Bacher, C. Reutenauer, The number of right ideals of given codimension over a finite field, in Noncommutative Birational Geometry, Representations and Combinatorics, edited by Arkady. Berenstein and Vladimir. Retakha, Contemporary Mathematics, Vol. 592, 2013.

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


Vaclav Kotesovec, Table of n, a(n) for n = 1..350

D. Callan, A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata, arXiv:0704.0004 [math.CO], 2007.

Andrew Elvey Price, Wenjie Fang, and Michael Wallner, Compacted binary trees admit a stretched exponential, arXiv:1908.11181 [math.CO], 2019-2020; J. Combin. Theory Ser. A 177 (2021), Paper No. 105306, 40 pp.

Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic enumeration of compacted binary trees of bounded right height, arXiv:1703.10031 [math.CO], 2017; J. Combin. Theory Ser. A 172 (2020), 105177, 49 pp.

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

Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017-2018; Theoret. Comput. Sci. 755 (2019), 1-12.


a(n) := c_2(n)/(n-1)! where c_2(n) := T_2(n, 1)-sum(binomial(n-1, j-1)*T_2(n-j, j+1)*c_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)^(2*n-2*i)*T_2(i, k), i=0..n-1), n>0.

Equals column 0 of triangle A102086. Also equals main diagonal of A102316: a(n) = A102086(n, 0) = A102316(n, n). - Paul D. Hanna, Jan 07 2005

G.f.: 1 = Sum_{n>=0} a(n)*x^n*prod_{k=1, n+1} (1-k*x) for n>0 with a(0)=1. a(n) = -Sum_{k=1, [(n+1)/2]} A008276(n-k+1, k)*a(n-k) where A008276 is Stirling numbers of the first kind. Thus G.f.: 1 = (1-x) + 1*x*(1-x)(1-2x) + 3*x^2*(1-x)(1-2x)(1-3x) + ... + a(n)*x^n*(1-x)(1-2x)(1-3x)*..*(1-(n+1)*x) + ... with a(0)=1. - Paul D. Hanna, Jan 14 2005

a(n) is the determinant of the n X n matrix with (i, j) entry = StirlingCycle[i+1, 2i-j]. - David Callan, Jul 20 2005

a(n) = b(n,0) where b(0,p) = p+1 and b(n+1,p) = Sum_{i=0..n} b(i,p)*b(n-i,p+i) for n>=1. - Michael Wallner, Apr 20 2017

From Michael Wallner, Jan 31 2022: (Start)

a(n) = r(n,n) where r(n,m)=(m+1)*r(n-1,m)+r(n,m-1) for n>=m>=1, r(n,m)=0 for n<m, and r(n,0)=1 for n>=0.

a(n) = Theta(n!*4^n*exp(3*a1*n^(1/3))*n) for large n, where a1=-2.338... is the largest root of the Airy function Ai(x) of the first kind; see [Elvey Price, Fang, Wallner 2021]. (End)


a(2)=3 since the following transition diagrams represent all three initially connected acyclic automata with two input letters x and y, two transient states 1 (initial) and 2 and the absorbing state 0:

1==x,y==>2==x,y==>0==x,y==>0, 1--x-->2==x,y==>0==x,y==>0


and the last one with x and y interchanged.


a[n_] := a[n] =  If[n == 0, 1, Coefficient[1-Sum[a[k]*x^k*Product[1-j*x, {j, 1, k+1}], {k, 0, n-1}], x, n]]; Table[a[n], {n, 1, 18}] (* Jean-Fran├žois Alcover, Dec 15 2014, after Paul D. Hanna *)


(PARI) {a(n)=if(n==0, 1, polcoeff(1-sum(k=0, n-1, a(k)*x^k*prod(j=1, k+1, 1-j*x+x*O(x^n))), n))} \\ Paul D. Hanna

(PARI) {a(n)=local(A); if(n<1, 0, A=x+x*O(x^n); for(k=0, n, A+=polcoeff(A, k)*x^k*(1-prod(i=1, k+1, 1-i*x))); polcoeff(A, n))} /* Michael Somos, Jan 16 2005 */


Cf. A082157.

Cf. A102086, A102316, A254789.

Sequence in context: A214645 A296535 A088358 * A264636 A208829 A289145

Adjacent sequences:  A082158 A082159 A082160 * A082162 A082163 A082164




Valery A. Liskovets, Apr 09 2003



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 06:50 EDT 2022. Contains 356987 sequences. (Running on oeis4.)