A082159 -id:A082159 - cp's OEIS frontend

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

1, 7, 315, 45682, 15646589, 10567689552, 12503979423607, 23841011541867520, 68835375121428936153, 286850872894190847235840, 1660638682341609286358474579, 12947089879912710544534553836032

Offset: 0

Valery A. Liskovets, Apr 09 2003

This is the first column of the array A082172.

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. A082159, A082158, A082172.

function a(n) // a = A082160
  if n eq 0 then return 1;
  else return (&+[Binomial(n,j)*(-1)^(n-j-1)*((j+2)^3 - 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)^3 - 1)^(n - i) a[i], {i, 0, n - 1}];
Table[a[n], {n, 0, 11}] (* Jean-François Alcover, Aug 29 2019 *)

@CachedFunction
def a(n): # A082160
    if n==0: return 1
    else: return sum(binomial(n,j)*(-1)^(n-j-1)*((j+2)^3 -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_3(n) where b_3(0) = 1, b_3(n) = Sum_{i=0..n-1} binomial(n, i)*(-1)^(n-i-1)*((i+2)^3 - 1)^(n-i)*b_3(i), n > 0.

A082171 A subclass of quasi-acyclic automata with 2 inputs, n transient and k absorbing labeled states; square array T(n,k) read by descending antidiagonals (n >= 0 and k >= 1).

Original entry on oeis.org

1, 1, 3, 1, 8, 39, 1, 15, 176, 1206, 1, 24, 495, 7784, 69189, 1, 35, 1104, 29430, 585408, 6416568, 1, 48, 2135, 84600, 2791125, 67481928, 881032059, 1, 63, 3744, 204470, 9841728, 389244600, 11111547520, 168514815360, 1, 80, 6111, 437616, 28569765, 1627740504, 75325337235, 2483829653544, 42934911510249

Offset: 0

Valery A. Liskovets, Apr 09 2003

Array read by descending antidiagonals: (0,1), (0,2), (1,1), (0,3), ...

The first column is A082159; i.e., T(n,k=1) = A082159(n). [The number n of transient states in the name of square array T(n,k) does not include the pre-dead transient state, which is, however, included in the name of A082159. See Section 3.1 in Liskovets (2006). - Petros Hadjicostas, Mar 07 2021]

			Array T(n,k) (with rows n >= 0 and columns k >= 1) begins:
          1,           1,           1,          1,        1, ...;
          3,           8,          15,         24,       35, ...;
         39,         176,         495,       1104,     2135, ...;
       1206,        7784,       29430,      84600,   204470, ...;
      69189,      585408,     2791125,    9841728, 28569765, ...;
    6416568,    67481928,   389244600, 1627740504, ...;
  881032059, 11111547520, 75325337235, ...;
  ...
Triangular array A(n,k) = T(k-1, n-k+1) (with rows n >= 1 and columns k = 1..n), read from the antidiagonals downwards of square array T:
  1;
  1,  3,
  1,  8,   39;
  1, 15,  176,  1206;
  1, 24,  495,  7784,   69189;
  1, 35, 1104, 29430,  585408,  6416568;
  1, 48, 2135, 84600, 2791125, 67481928, 881032059;
  ...

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. A082159, A082163, A082169.

function A(n,k)
  if n eq 0 then return 1;
  else return (&+[(-1)^(n-j+1)*Binomial(n,j)*((k+j+1)^2-1)^(n-j)*A(j,k): j in [0..n-1]]);
  end if;
end function;
A082171:= func< n,k | A(k,n-k+1) >;
[A082171(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)^2 - 1)^(n - i)*T[i, k], {i, 0, n - 1}];
Table[T[n - k - 1, k], {n, 1, 10}, {k, n - 1, 1, -1}] // Flatten (* Jean-François Alcover, Aug 29 2019 *)

lista(nn,kk)={my(T=matrix(nn+1,kk)); for(n=1, nn+1, for(k=1, kk, 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])))); T;} \\ Petros Hadjicostas, Mar 07 2021

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

T(n, k) = S_2(n, k) where S_2(0, k) := 1 and S_2(n, k) := Sum_{i=0..n-1} binomial(n, i)*(-1)^(n-i-1)*((i + k + 1)^2 - 1)^(n-i)*S_2(i, k) for n > 0.

Name clarified by Petros Hadjicostas, Mar 07 2021

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

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.

Original entry on oeis.org

1, 3, 15, 114, 1191, 15993, 263976, 5189778, 118729335, 3104549229, 91472523339, 3002047651764, 108699541743348, 4307549574285900, 185545521930558012, 8636223446937857130, 432133295481763698951, 23140414627731672497973, 1320835234697505382760757, 80076275471464881277266666, 5139849930933791535446756127

Offset: 1

Valery A. Liskovets, Apr 09 2003

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

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.]
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. A082159, A082161, A082171, A103236.

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,
n-1}]]]; Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Dec 15 2014, after 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
/* Second PARI program using Valery A. Liskovets's recurrence: */
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

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

More terms from Petros Hadjicostas, Mar 06 2021 using the above programs

cp's OEIS Frontend

A082160 Deterministic completely defined acyclic automata with 3 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

SageMath

Formula

A082171 A subclass of quasi-acyclic automata with 2 inputs, n transient and k absorbing labeled states; square array T(n,k) read by descending antidiagonals (n >= 0 and k >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

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

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions