A082171 -id:A082171 - 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.

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

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.

A103242 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)^2)^(n-k)/(n-k)! for n >= k >= 1.

Original entry on oeis.org

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

Offset: 1

Paul D. Hanna, Feb 02 2005

Define a triangular matrix P where P(n,k) = (-k^2-2*k)^(n-k)/(n-k)!; then M = P*D*P^-1 = A103236 satisfies M^2 + 2*M = 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 A082171 as a triangular matrix. The first column is A082163 (enumerates acyclic automata with 2 inputs).

			Rows of unreduced fractions T(n,k)/(n-k)! begin:
  [1/0!],
  [3/1!, 1/0!],
  [39/2!, 8/1!, 1/0!],
  [1206/3!, 176/2!, 15/1!, 1/0!],
  [69189/4!, 7784/3!, 495/2!, 24/1!, 1/0!],
  [6416568/5!, 585408/4!, 29430/3!, 1104/2!, 35/1!, 1/0!], ...
forming the inverse of matrix P where P(n,k) = A103247(n,k)/(n-k)!:
  [1/0!],
  [ -3/1!, 1/0!],
  [9/2!, -8/1!, 1/0!],
  [ -27/3!, 64/2!, -15/1!, 1/0!],
  [81/4!, -512/3!, 225/2!, -24/1!, 1/0!],
  [ -243/5!, 4096/4!, -3375/3!, 576/2!, -35/1!, 1/0!], ...

Cf. A103247, A103236, A082171, A082163.

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

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

For n > k >= 1: 0 = Sum_{j=k..n} C(n-k, j-k)*(1-(k+1)^2)^(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

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

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

A103242 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)^2)^(n-k)/(n-k)! for n >= k >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula