A082170 -id:A082170 - cp's OEIS frontend

A082162 Number of deterministic completely defined initially connected acyclic automata with 3 inputs and n transient unlabeled states (and a unique absorbing state).

Original entry on oeis.org

1, 7, 139, 5711, 408354, 45605881, 7390305396, 1647470410551, 485292763088275, 183049273155939442, 86211400693272461866

Offset: 1

Valery A. Liskovets, Apr 09 2003

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

R. Bacher, C. Reutenauer, The number of right ideals of given codimension over a finite field, in Noncommutative Birational Geometry, Representations and Combinatorics, edited by Arkady. Berenstein and Vladimir. Retakha, Contemporary Mathematics, Vol. 592, 2013.

Vaclav Kotesovec (after Jean-François Alcover), Table of n, a(n) for n = 1..210
Manosij Ghosh Dastidar and Michael Wallner, Asymptotics of relaxed k-ary trees, arXiv:2404.08415 [math.CO], 2024. See p. 1.4.
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. A082158, A082161.

Cf. A102098, A102400.

T[n_, k_] := T[n, k] = If[nJean-François Alcover, Dec 15 2014 *)

a(n) = c_3(n)/(n-1)! where c_3(n) = T_3(n, 1) - sum(binomial(n-1, j-1)*T_3(n-j, j+1)*c_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)^(3*n-3*i)*T_3(i, k), i=0..n-1), n>0.

Equals column 0 of triangle A102098. Also equals main diagonal of A102400: a(n) = A102098(n, 0) = A102400(n, n). - Paul D. Hanna, Jan 07 2005

More terms from Paul D. Hanna, Jan 07 2005

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.

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

Original entry on oeis.org

1, 1, 1, 15, 8, 1, 1024, 368, 27, 1, 198581, 53672, 2727, 64, 1, 85102056, 18417792, 710532, 11904, 125, 1, 68999174203, 12448430408, 386023509, 4975936, 38375, 216, 1, 95264160938080, 14734002979456, 381535651512, 3977848832, 23945000

Offset: 1

Paul D. Hanna, Feb 02 2005

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

			Rows of unreduced fractions T(n,k)/(n-k)! begin:
  [1/0!],
  [1/1!, 1/0!],
  [15/2!, 8/1!, 1/0!],
  [1024/3!, 368/2!, 27/1!, 1/0!],
  [198581/4!, 53672/3!, 2727/2!, 64/1!, 1/0!],
  [85102056/5!, 18417792/4!, 710532/3!, 11904/2!, 125/1!, 1/0!], ...
forming the inverse of matrix P where P(n,k) = A103246(n,k)/(n-k)!:
  [1/0!],
  [-1/1!, 1/0!],
  [1/2!, -8/1!, 1/0!],
  [-1/3!, 64/2!, -27/1!, 1/0!],
  [1/4!, -512/3!, 729/2!, -64/1!, 1/0!], ...

Cf. A103246, A102098, A082170, A082162.

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

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

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

cp's OEIS Frontend

A082162 Number of deterministic completely defined initially connected acyclic automata with 3 inputs and n transient unlabeled states (and a unique absorbing state).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

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

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula