|
%I #70 Apr 18 2024 12:50:31
%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 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 (SageMath)
%o @CachedFunction
%o def b(n,k):
%o if n==0: return k+1
%o else: 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 [A082161(n) for n in range(1,31)] # _G. C. Greubel_, Jan 18 2024
%Y Cf. A008276, A082157, A082169, A102086, A102316, A254789.
%K easy,nonn,changed
%O 1,2
%A _Valery A. Liskovets_, Apr 09 2003
|
