|
| |
|
|
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, 8636223446937857130, 432133295481763698951, 23140414627731672497973, 1320835234697505382760757, 80076275471464881277266666, 5139849930933791535446756127
(list;
graph;
refs;
listen;
history;
text;
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 leftmost 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, Jan 29 2005
|
|
|
LINKS
|
Valery A. Liskovets, The number of connected initial automata, Kibernetika (Kiev), 3 (1969), 16-19 (in Russian; English translation: Cybernetics, 4 (1969), 259-262). [It includes the original methodology that he used in his 2003 and 2006 papers.]
|
|
|
FORMULA
|
a(1) = 1 and a(n) := d_2(n-1)/(n-2)! for n >= 2, where d_2(n) := T_2(n, 1) - Sum_{j=1..n-1} binomial(n-1, j-1) * T_2(n-j, j+1) * d_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+1)^2 - 1)^(n-i) * T_2(i, k) for n > 0. [Edited by Petros Hadjicostas, Mar 06 2021 to agree with Theorem 3.3 (p. 543) in Liskovets (2006). Here, n + 1 is "the number of transient states including the pre-dead state".]
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, Jan 29 2005
|
|
|
MATHEMATICA
|
a[n_] := a[n] = If[n<1, 0, If[n == 1, 1, SeriesCoefficient[1-Sum[a[k+1]*x^k/(1-2*x)^k*Product[1-(j+3)*x, {j, 0, k}], {k, 0, n-2}], {x, 0,
|
|
|
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)))} \\ Paul D. Hanna, Jan 29 2005
lista(nn)={my(T=matrix(nn+1, nn+1)); my(d=vector(nn)); my(a=vector(nn)); for(n=1, nn+1, for(k=1, nn, T[n, k] = if(n==1, 1, sum(i=0, n-2, binomial(n-1, i)*(-1)^(n-i-2)*((i + k + 1)^2 - 1)^(n-i-1)*T[i+1, k])))); for(n=1, nn, d[n] = T[n+1, 1] - sum(j=1, n-1, binomial(n-1, j-1)*T[n-j+1, j+1]*d[j])); for(n=1, nn, a[n] = if(n==1, 1, d[n-1]/(n-2)!)); a; } \\ Petros Hadjicostas, Mar 07 2021
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
