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

%I #79 Oct 26 2024 16:08:30

%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 Roland Bacher and Christophe 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.

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

%H David Callan, <a href="https://arxiv.org/abs/0704.0004">A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata</a>, arXiv:0704.0004 [math.CO], 2007.

%H Manosij Ghosh Dastidar and Michael Wallner, <a href="https://arxiv.org/abs/2404.08415">Asymptotics of relaxed k-ary trees</a>, arXiv:2404.08415 [math.CO], 2024. See p. 1.4.

%H Andrew Elvey Price, Wenjie Fang, and Michael Wallner, <a href="https://arxiv.org/abs/1908.11181">Compacted binary trees admit a stretched exponential</a>, arXiv:1908.11181 [math.CO], 2019-2020; J. Combin. Theory Ser. A 177 (2021), Paper No. 105306, 40 pp.

%H Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, <a href="https://arxiv.org/abs/1703.10031">Asymptotic enumeration of compacted binary trees of bounded right height</a>, arXiv:1703.10031 [math.CO], 2017; J. Combin. Theory Ser. A 172 (2020), 105177, 49 pp.

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

%H Fedor Petrov, <a href="https://mathoverflow.net/a/477153/231922">On a generating function and vector ν of length n</a>, answer to question on MathOverflow (2024).

%H Michael Wallner, <a href="https://arxiv.org/abs/1706.07163">A bijection of plane increasing trees with relaxed binary trees of right height at most one</a>, arXiv:1706.07163 [math.CO], 2017-2018; Theoret. Comput. Sci. 755 (2019), 1-12.

%F a(n) = c_2(n)/(n-1)! where c_2(n) = T_2(n, 1) - Sum_{j=1..n-1} binomial(n-1, j-1)*T_2(n-j, j+1)*c_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)^(2*n-2*i)*T_2(i, k), 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

%F From _Michael Wallner_, Jan 31 2022: (Start)

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

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

%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]];

%t Table[a[n], {n, 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_, Jan 07 2005

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

%o (Python)

%o from functools import cache

%o @cache

%o def b(n, k):

%o if n == 0: return k + 1

%o return sum(b(j, k)*b(n-j-1, k+j) for j in range(n))

%o def A082161(n): return b(n, 0)

%o print([A082161(n) for n in range(1, 19)]) # G. C. Greubel, Jan 18 2024

%o (PARI) upto(n) = my(v=vector(n+1, i, i==1)); for(i=1, n, for(j=i+1, n+1, v[j] += i*v[j-1])); v[2..#v] \\ _Mikhail Kurkov_, Oct 25 2024

%Y Cf. A008276, A082157, A082169, A102086, A102316, A254789.

%K easy,nonn

%O 1,2

%A _Valery A. Liskovets_, Apr 09 2003