A082160 -id:A082160 - cp's OEIS frontend

A082159 Number of deterministic completely defined acyclic automata with 2 inputs and n+1 transient labeled states including a unique state having all transitions to the absorbing state.

1, 3, 39, 1206, 69189, 6416568, 881032059, 168514815360, 42934911510249, 14081311783382400, 5786296490491543599, 2914663547018935095552, 1767539279001227299807725, 1271059349855055258673975296, 1069996840045068513065229943875

Offset: 0

Valery A. Liskovets, Apr 09 2003

This is the first column of the array A082171.

G. C. Greubel, Table of n, a(n) for n = 0..150
Valery A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
Valery A. Liskovets, Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, No.3 (2006), 537-551.

Cf. A082157, A082160, A082171.

function a(n) // a = A082159
  if n eq 0 then return 1;
  else return (&+[Binomial(n,j)*(-1)^(n-j-1)*((j+2)^2 - 1)^(n-j)*a(j): j in [0..n-1]]);
  end if;
end function;
[a(n): n in [0..20]]; // G. C. Greubel, Jan 17 2024

a[0] = 1; a[n_] := a[n] = Sum[Binomial[n, i] (-1)^(n - i - 1) ((i + 2)^2 - 1)^(n - i) a[i], {i, 0, n - 1}];
Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Aug 29 2019 *)

lista(nn)={my(a=vector(nn+1)); for(n=1, nn+1, a[n] = if(n==1, 1, sum(i=0, n-2, binomial(n-1, i)*(-1)^(n-i-2)*((i + 2)^2 - 1)^(n-i-1)*a[i+1]))); a;} \\ Petros Hadjicostas, Mar 07 2021

@CachedFunction
def a(n): # A082159
    if n==0: return 1
    else: return sum(binomial(n,j)*(-1)^(n-j-1)*((j+2)^2 -1)^(n-j)*a(j) for j in range(n))
[a(n) for n in range(21)] # G. C. Greubel, Jan 17 2024

a(n) = b_2(n), where b_2(0) = 1 and b_2(n) = Sum_{0..n-1} binomial(n, i) * (-1)^(n-i-1) * ((i + 2)^2 - 1)^(n-i) * b_2(i) for n > 0.

A082158 Number of deterministic completely defined acyclic automata with 3 inputs and n transient labeled states (and a unique absorbing state).

Original entry on oeis.org

1, 1, 15, 1024, 198581, 85102056, 68999174203, 95264160938080, 207601975572545961, 674354204416939196800, 3122476748685067008205511, 19884561572783089348189507584, 169123749545536919971662851459485, 1874777145334671354828947023095675904, 26531967154935836079418311035871122812275

Offset: 0

Valery A. Liskovets, Apr 09 2003

This is the first column of the array A082170.

G. C. Greubel, Table of n, a(n) for n = 0..150
Valery A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
Valery A. Liskovets, Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, No.3 (2006), 537-551.

Cf. A082157, A082159, A082160, A082170.

function a(n) // a = A082158
  if n eq 0 then return 1;
  else return (&+[Binomial(n,j)*(-1)^(n-j-1)*(j+1)^(3*n-3*j)*a(j): j in [0..n-1]]);
  end if;
end function;
[a(n): n in [0..20]]; // G. C. Greubel, Jan 17 2024

a[n_] := If[n == 0, 1, Sum[-(-1)^(n-k) Binomial[n, k] (k+1)^(3(n-k)) a[k], {k, 0, n-1}]];
Table[a[n], {n, 0, 11}] (* Jean-François Alcover, Aug 29 2019 *)

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+(k+1)^3*x+x*O(x^n))^(k+1)), n)}
for(n=0,20,print1(a(n),", ")) \\ Paul D. Hanna, May 03 2015

{a(n)=if(n==0, 1, sum(k=0, n-1, -(-1)^(n-k)*binomial(n, k)*(k+1)^(3*(n-k))*a(k)))}
for(n=0,20,print1(a(n),", ")) \\ Paul D. Hanna, May 03 2015

@CachedFunction
def a(n): # A082158
    if n==0: return 1
    else: return sum(binomial(n,j)*(-1)^(n-j-1)*(j+1)^(3*n-3*j)*a(j) for j in range(n))
[a(n) for n in range(21)] # G. C. Greubel, Jan 17 2024

a(n) = a_3(n) where a_3(0) = 1, a_3(n) = Sum_{i=0..n-1} binomial(n, i)*(-1)^(n-i-1)*(i+1)^(3*n-3*i)*a_3(i), n > 0.
1 = Sum_{n>=0} a(n)*exp(-(1+n)^3*x)*x^n/n!. - Vladeta Jovovic, Jul 18 2005
From Paul D. Hanna, May 03 2015: (Start)
1 = Sum_{n>=0} a(n) * x^n/(1 + (n+1)^3*x)^(n+1).
1 = Sum_{n>=0} a(n) * C(n+m-1,n) * x^n/(1 + (n+1)^3*x)^(n+m) for all m>=1.
log(1+x) = Sum_{n>=1} a(n) * x^n/(1 + (n+1)^3*x)^n/n. (End)

More terms from Michel Marcus, Aug 29 2019

A082172 A subclass of quasi-acyclic automata with 3 inputs, n transient and k absorbing labeled states.

Original entry on oeis.org

1, 1, 7, 1, 26, 315, 1, 63, 2600, 45682, 1, 124, 11655, 675194, 15646589, 1, 215, 37944, 4861458, 366349152, 10567689552, 1, 342, 100835, 23641468, 3882676581, 361884843866, 12503979423607, 1, 511, 232560, 89076650, 26387681120, 5318920238688, 591934698991168, 23841011541867520

Offset: 0

Valery A. Liskovets, Apr 09 2003

Array read by antidiagonals: (0,1),(0,2),(1,1),(0,3),... . The first column is A082160.

			The array begins:
               1,            1,          1,           1,        1, ...;
               7,           26,         63,         124,      215, ...;
             315,         2600,      11655,       37944,   100835, ...;
           45682,       675194,    4861458,    23641468, 89076650, ...;
        15646589,    366349152, 3882676581, 26387681120, ...;
     10567689552, 361884843866, ...;
  12503979423607,  ...;
Antidiagonals begin as:
  1;
  1,   7;
  1,  26,    315;
  1,  63,   2600,    45682;
  1, 124,  11655,   675194,   15646589;
  1, 215,  37944,  4861458,  366349152,  10567689552;
  1, 342, 100835, 23641468, 3882676581, 361884843866, 12503979423607;

G. C. Greubel, Antidiagonals n = 0..50, flattened
Valery A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
Valery A. Liskovets, Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, No.3 (2006), 537-551.

Cf. A082160, A082164, A082170, A082171.

function A(n,k)
  if n eq 0 then return 1;
  else return (&+[(-1)^(n-j+1)*Binomial(n,j)*((k+j+1)^3-1)^(n-j)*A(j,k): j in [0..n-1]]);
  end if;
end function;
A082172:= func< n,k | A(k,n-k+1) >;
[A082172(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jan 19 2024

T[0, ] = 1; T[n, k_] := T[n, k] = Sum[Binomial[n, i]*(-1)^(n - i - 1)*((i + k + 1)^3 - 1)^(n - i)*T[i, k], {i, 0, n - 1}];
Table[T[n-k, k], {n, 1, 9}, {k, n, 1, -1}]//Flatten (* Jean-François Alcover, Aug 27 2019 *)

@CachedFunction
def A(n,k):
    if n==0: return 1
    else: return sum((-1)^(n-j+1)*binomial(n,j)*((k+j+1)^3-1)^(n-j)*A(j,k) for j in range(n))
def A082172(n,k): return A(k,n-k+1)
flatten([[A082172(n,k) for k in range(n+1)] for n in range(12)]) # G. C. Greubel, Jan 19 2024

T(n, k) = S_3(n, k) where S_3(0, k) = 1, S_3(n, k) = Sum_{i=0..n-1} (-1)^(n-i-1)*binomial(n, i)*((i+k+1)^3-1)^(n-i)*S_3(i, k), n > 0.

A082164 Deterministic completely defined initially connected acyclic automata with 3 inputs and n+1 transient unlabeled states including a unique state having all transitions to the absorbing state.

Original entry on oeis.org

1, 7, 133, 5362, 380093, 42258384, 6830081860, 1520132414241, 447309239576913, 168599289097947589, 79364534944804317166, 45701029702436877135199, 31642128418550547009710906, 25960688434777959685891570936, 24926392120419324125117256758595, 27708074645788511889179577045508824

Offset: 1

Valery A. Liskovets, Apr 09 2003

Coefficients T_2(n,k) form the array A082172. These automata have no nontrivial automorphisms (by states).

V. A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
V. A. Liskovets, Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, No.3 (2006), 537-551.

Cf. A082160, A082163, A082162.

b[, 0, ] = 1; b[k_, n_, r_] := b[k, n, r] = Sum[Binomial[n, t] (-1)^(n - t - 1) ((t + r + 1)^k - 1)^(n - t) b[k, t, r], {t, 0, n - 1}];
d3[n_] := d3[n] = b[3, n, 1] - Sum[Binomial[n - 1, j - 1] T3[n - j, j + 1] d3[j], {j, 1, n - 1}];
T3[0, ] = 1; T3[n, k_] := T3[n, k] = Sum[Binomial[n, i] (-1)^(n - i - 1) ((i + k + 1)^3 - 1)^(n - i) T3[i, k], {i, 0, n - 1}];
a[n_] := If[n == 1, 1, d3[n - 1]/(n - 2)!];
Array[a, 20] (* Jean-François Alcover, Aug 29 2019 *)

a(n) := d_3(n)/(n-1)! where d_3(n) := b_3(n, 1)-sum(binomial(n-1, j-1)*T_3(n-j, j+1)*d_3(j), j=1..n-1); and T_3(0, k) := 1, T_3(n, k) := sum(binomial(n, i)*(-1)^(n-i-1)*((i+k+1)^3-1)^(n-i)*T_3(i, k), i=0..n-1), n>0.

More terms from Jean-François Alcover, Aug 29 2019

A103243 Unreduced numerators of the elements T(n,k)/(n-k)!, read by rows, of the triangular matrix P^-1, which is the inverse of the matrix defined by P(n,k) = (1-(k+1)^3)^(n-k)/(n-k)! for n >= k >= 1.

Original entry on oeis.org

1, 7, 1, 315, 26, 1, 45682, 2600, 63, 1, 15646589, 675194, 11655, 124, 1, 10567689552, 366349152, 4861458, 37944, 215, 1, 12503979423607, 361884843866, 3882676581, 23641468, 100835, 342, 1, 23841011541867520, 591934698991168, 5318920238688

Offset: 1

Paul D. Hanna, Feb 02 2005

Define triangular matrix P by P(n,k) = (-k^3-3k^2-3k)^(n-k)/(n-k)!, then M = P*D*P^-1 = A103237 satisfies: M^3 + 3M^2 + 3M = SHIFTUP(M) where D is the diagonal matrix consisting of {1,2,3,...}. The operation SHIFTUP(M) shifts each column of M up 1 row. Essentially equal to square array A082172 as a triangular matrix. The first column is A082160 (quasi-acyclic automata with 3 inputs).

			Rows of unreduced fractions T(n,k)/(n-k)! begin:
  [1/0! ],
  [7/1!, 1/0! ],
  [315/2!, 26/1!, 1/0! ],
  [45682/3!, 2600/2!, 63/1!, 1/0! ],
  [15646589/4!, 675194/3!, 11655/2!, 124/1!, 1/0! ],
  [10567689552/5!, 366349152/4!, 4861458/3!, 37944/2!, 215/1!, 1/0! ], ...
forming the inverse of matrix P where P(n,k) = A103247(n,k)/(n-k)!:
  [1/0! ],
  [ -7/1!, 1/0! ],
  [49/2!, -26/1!, 1/0! ],
  [ -343/3!, 676/2!, -63/1!, 1/0! ],
  [2401/4!, -17576/3!, 3969/2!, -124/1!, 1/0! ],
  [ -16807/5!, 456976/4!, -250047/3!, 15376/2!, -215/1!, 1/0! ], ...

Cf. A103248, A103237, A082172, A082160.

{T(n,k)=my(P);if(n>=k&k>=1, P=matrix(n,n,r,c,if(r>=c,(1-(c+1)^3)^(r-c)/(r-c)!))); return(if(n

For n > k >= 1: 0 = Sum_{m=k..n} C(n-k, m-k)*(1-(m+1)^3)^(n-m)*T(m, k). For n > k >= 1: 0 = Sum_{j=k..n} C(n-k, j-k)*(1-(k+1)^3)^(j-k)*T(n, j).

cp's OEIS Frontend

A082159 Number of deterministic completely defined acyclic automata with 2 inputs and n+1 transient labeled states including a unique state having all transitions to the absorbing state.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A082158 Number of deterministic completely defined acyclic automata with 3 inputs and n transient labeled states (and a unique absorbing state).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

SageMath

Formula

Extensions

A082172 A subclass of quasi-acyclic automata with 3 inputs, n transient and k absorbing labeled states.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A082164 Deterministic completely defined initially connected acyclic automata with 3 inputs and n+1 transient unlabeled states including a unique state having all transitions to the absorbing state.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A103243 Unreduced numerators of the elements T(n,k)/(n-k)!, read by rows, of the triangular matrix P^-1, which is the inverse of the matrix defined by P(n,k) = (1-(k+1)^3)^(n-k)/(n-k)! for n >= k >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula