|
|
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)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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
|
|
REFERENCES
|
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.
|
|
LINKS
|
|
|
FORMULA
|
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.
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
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)
|
|
EXAMPLE
|
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
1 -- y --> 0
and the last one with x and y interchanged.
|
|
MATHEMATICA
|
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]];
|
|
PROG
|
(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
(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 */
(SageMath)
@CachedFunction
def b(n, k):
if n==0: return k+1
else: return sum(b(j, k)*b(n-j-1, k+j) for j in range(n))
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|