A103236 -id:A103236 - cp's OEIS frontend

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.

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

A103237 Triangular matrix T, read by rows, that satisfies: T^3 + 3T^2 + 3T = SHIFTUP(T), also T^(n+2) + 3T^(n+1) + 3T^n = SHIFTUP(T^n - D*T^(n-1)) for all n, where D is a diagonal matrix with diagonal(D) = diagonal(T) = {1,2,3,...}.

Original entry on oeis.org

1, 7, 2, 133, 26, 3, 5362, 962, 63, 4, 380093, 66794, 3843, 124, 5, 42258384, 7380100, 409248, 11284, 215, 6, 6830081860, 1190206134, 65160081, 1709836, 27305, 342, 7, 1520132414241, 264665899160, 14416260516, 371199704, 5585270, 57798, 511, 8

Offset: 0

Paul D. Hanna, Jan 31 2005

Leftmost column is A082164 (enumerates acyclic automata with 3 inputs). The operation SHIFTUP(T) shifts each column of T up 1 row, dropping the elements that occupied the diagonal of T.

			Rows of T begin:
[1],
[7,2],
[133,26,3],
[5362,962,63,4],
[380093,66794,3843,124,5],
[42258384,7380100,409248,11284,215,6],
[6830081860,1190206134,65160081,1709836,27305,342,7],...
Rows of T^2 begin:
[1],
[21,4],
[714,130,9],
[41923,7410,441,16],...
Rows of T^3 begin:
[1],
[49,8],
[2821,494,27],
[238238,41678,2331,64],...
Rows of T^3 + 3*T^2 + 3*T equals SHIFTUP(T):
[7],
[133,26],
[5362,962,63],
[380093,66794,3843,124],...

Cf. A082164, A103248, A103243, A103236.

{T(n,k)=local(P,D);D=matrix(n+1,n+1,r,c,if(r==c,r)); P=matrix(n+1,n+1,r,c,if(r>=c,(-1)^(r-c)*(c^3+3*c^2+3*c)^(r-c)/(r-c)!)); return(if(n

T = P*D*P^-1 where P(r, c) = A103248(r, c)/(r-c)! = (-1)^(r-c)*(c^3+3*c^2+3*c)^(r-c)/(r-c)! for r>=c>=1 and [P^-1](r, c) = A103243(r, c)/(r-c)! and D is a diagonal matrix = {1, 2, 3, ...}.

A103238 Triangular matrix T, read by rows, that satisfies: T^2 + T = SHIFTUP(T), also T^(n+1) + T^n = SHIFTUP(T^n - D*T^(n-1)) for all n, where D is a diagonal matrix with diagonal(D) = diagonal(T) = {1,2,3,...}.

Original entry on oeis.org

1, 2, 2, 8, 6, 3, 52, 36, 12, 4, 480, 324, 96, 20, 5, 5816, 3888, 1104, 200, 30, 6, 87936, 58536, 16320, 2800, 360, 42, 7, 1601728, 1064016, 294048, 49200, 5940, 588, 56, 8, 34251520, 22728384, 6252288, 1032800, 120960, 11172, 896, 72, 9, 843099616

Offset: 0

Paul D. Hanna, Jan 31 2005

Leftmost column is A103239. The operation SHIFTUP(T) shifts each column of T up 1 row, dropping the elements that occupied the diagonal of T.

			Rows of T begin:
[1],
[2,2],
[8,6,3],
[52,36,12,4],
[480,324,96,20,5],
[5816,3888,1104,200,30,6],
[87936,58536,16320,2800,360,42,7],
[1601728,1064016,294048,49200,5940,588,56,8],...
Rows of T^2 begin:
[1],
[6,4],
[44,30,9],
[428,288,84,16],
[5336,3564,1008,180,25],...
Then T^2 + T = SHIFTUP(T):
[2],
[8,6],
[52,36,12],
[480,324,96,20],
[5816,3888,1104,200,30],...
G.f. for column 0: 1 = (1-2x) + 2*x/(1-x)*(1-2x)(1-3x) + 8*x^2/(1-x)^2*(1-2x)(1-3x)(1-4x) + 52*x^3/(1-x)^3*(1-2x)(1-3x)(1-4x)(1-5x) + ... + T(n,0)*x^n/(1-x)^n*(1-2x)(1-3x)*..*(1-(n+2)x) + ...
G.f. for column 1: 2 = 2*(1-3x) + 6*x/(1-x)*(1-3x)(1-4x) + 36*x^2/(1-x)^2*(1-3x)(1-4x)(1-5x) + 324*x^3/(1-x)^3*(1-3x)(1-4x)(1-5x)(1-6x) + ... + T(n,1)*x^(n-1)/(1-x)^(n-1)*(1-3x)(1-4x)*..*(1-(n+2)x) + ...

Cf. A103239, A103244, A103249, A103236, A103237.

/* Using Matrix Diagonalization Formula: */ T(n,k)=my(P,D);D=matrix(n+1,n+1,r,c,if(r==c,r)); P=matrix(n+1,n+1,r,c,if(r>=c,(-1)^(r-c)*(c^2+c)^(r-c)/(r-c)!)); return(if(n

/* Using Generating Function for Columns: */ T(n,k)=if(n

G.f. for column k: T(k, k) = k+1 = Sum_{n>=k} T(n, k)*x^(n-k)/(1-x)^(n-k) * Product_{j=0..n-k} (1-(j+k+2)*x). Diagonalization: T = P*D*P^-1 where P(r, c) = A103249(r, c)/(r-c)! = (-1)^(r-c)*(c^2+c)^(r-c)/(r-c)! for r>=c>=1 and [P^-1](r, c) = A103244(r, c)/(r-c)! and D is a diagonal matrix = {1, 2, 3, ...}.

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

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

A103237 Triangular matrix T, read by rows, that satisfies: T^3 + 3T^2 + 3T = SHIFTUP(T), also T^(n+2) + 3T^(n+1) + 3T^n = SHIFTUP(T^n - D*T^(n-1)) for all n, where D is a diagonal matrix with diagonal(D) = diagonal(T) = {1,2,3,...}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A103238 Triangular matrix T, read by rows, that satisfies: T^2 + T = SHIFTUP(T), also T^(n+1) + T^n = SHIFTUP(T^n - D*T^(n-1)) for all n, where D is a diagonal matrix with diagonal(D) = diagonal(T) = {1,2,3,...}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

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