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!)
A082161 Number of deterministic completely defined initially connected acyclic automata with 2 inputs and n transient unlabeled states (and a unique absorbing state). 22

%I

%S 1,3,16,127,1363,18628,311250,6173791,142190703,3737431895,

%T 110577492346,3641313700916,132214630355700,5251687490704524,

%U 226664506308709858,10568175957745041423,529589006347242691143,28395998790096299447521

%N Number of deterministic completely defined initially connected acyclic automata with 2 inputs and n transient unlabeled states (and a unique absorbing state).

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

%C 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

%D 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.

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

%H Vaclav Kotesovec, <a href="/A082161/b082161.txt">Table of n, a(n) for n = 1..350</a>

%H D. Callan, <a href="http://arXiv.org/abs/0704.0004">A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata</a>

%H Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, <a href="https://arxiv.org/abs/1703.10031">Asymptotic Enumeration of Compacted Binary Trees</a>, arXiv:1703.10031 [math.CO], 2017

%H V. 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.

%H Michael Wallner, <a href="https://arxiv.org/abs/1703.10031">A bijection of plane increasing trees with relaxed binary trees of right height at most one</a>, arXiv:1706.07163 [math.CO], 2017

%F 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.

%F 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

%F 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

%F 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

%F 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

%e 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:

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

%e 1--y-->0

%e and the last one with x and y interchanged.

%t 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_ *)

%o (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_

%o (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 */

%Y Cf. A082157.

%Y Cf. A102086, A102316, A254789.

%K easy,nonn

%O 1,2

%A _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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 24 16:47 EST 2020. Contains 331209 sequences. (Running on oeis4.)