|
| |
|
|
A082163
|
|
Number of deterministic completely defined initially connected acyclic automata with 2 inputs and n+1 transient unlabeled states including a unique state having all transitions to the absorbing state.
|
|
4
| |
|
|
1, 3, 15, 114, 1191, 15993, 263976, 5189778, 118729335, 3104549229, 91472523339, 3002047651764, 108699541743348, 4307549574285900, 185545521930558012
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Coefficients T_2(n,k) form the array A082171. These automata have no nontrivial automorphisms (by states).
Also equals the left-most column of triangular matrix M=A103236, which satisfies: M^2 + 2*M = SHIFTUP(M) (i.e. each column of M shifts up 1 row). - Paul D. Hanna (pauldhanna(AT)juno.com), Jan 29 2005
|
|
|
REFERENCES
| V. A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
|
|
|
LINKS
| V. A. Liskovets, Exact enumeration of acyclic deterministic automata,Discrete Appl. Math., 154, No.3 (2006), 537-551.
|
|
|
FORMULA
| a(n) := d_2(n)/(n-1)! where d_2(n) := T_2(n, 1)-sum(binomial(n-1, j-1)*T_2(n-j, j+1)*d_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+1)^2-1)^(n-i)*T_2(i, k), i=0..n-1), n>0.
G.f.: 1 = Sum_{n>=0} a(n+1)*x^n/(1-2*x)^n*Product_{k=0..n} (1-(3+k)*x). Thus: 1 = 1*(1-3x) + 3*x/(1-2x)*(1-3x)(1-4x) + 15*x^2/(1-2x)^2*(1-3x)(1-4x)(1-5x) + 114*x^3/(1-2x)^3*(1-3x)(1-4x)(1-5x)(1-6x) + ... - Paul D. Hanna (pauldhanna(AT)juno.com), Jan 29 2005
|
|
|
PROG
| (PARI) {a(n)=if(n<1, 0, if(n==1, 1, polcoeff( 1-sum(k=0, n-2, a(k+1)*x^k/(1-2*x)^k*prod(j=0, k, 1-(j+3)*x+x*O(x^n))), n-1)))} (Hanna)
|
|
|
CROSSREFS
| Cf. A082159, A082161.
Cf. A103236.
Sequence in context: A059849 A123853 A166885 * A190629 A074596 A087806
Adjacent sequences: A082160 A082161 A082162 * A082164 A082165 A082166
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| Valery Liskovets (liskov(AT)im.bas-net.by), Apr 09 2003
|
| |
|
|
