A082162 -id:A082162 - cp's OEIS frontend

A102098 Triangular matrix, read by rows, that satisfies: T(n,k) = [T^3](n-1,k) when n>k>=0, with T(n,n) = (n+1).

1, 1, 2, 7, 8, 3, 139, 152, 27, 4, 5711, 6200, 999, 64, 5, 408354, 442552, 69687, 3904, 125, 6, 45605881, 49399320, 7724835, 416704, 11375, 216, 7, 7390305396, 8003532512, 1248465852, 66464960, 1725875, 27432, 343, 8, 1647470410551

Offset: 0

Paul D. Hanna, Dec 29 2004

Column 0 forms A082162. Column 1 forms A102099. Row sums form A102100. This triangle is a variant of A102086.

			Rows of T begin:
[1],
[1,2],
[7,8,3],
[139,152,27,4],
[5711,6200,999,64,5],
[408354,442552,69687,3904,125,6],
[45605881,49399320,7724835,416704,11375,216,7],
[7390305396,8003532512,1248465852,66464960,1725875,27432,343,8],...
Matrix cube T^3 equals T excluding the main diagonal:
[1],
[7,8],
[139,152,27],
[5711,6200,999,64],
[408354,442552,69687,3904,125],...

Cf. A082162, A102099, A102100, A102086.

{T(n,k)=local(A=matrix(1,1),B);A[1,1]=1; for(m=2,n+1,B=matrix(m,m);for(i=1,m, for(j=1,i, if(j==i,B[i,j]=j,if(j==1,B[i,j]=(A^3)[i-1,1], B[i,j]=(A^3)[i-1,j]));));A=B);return(A[n+1,k+1])}

T(n, 0) = A082162(n) for n>0, with T(0, 0) = 1.

A082170 Deterministic completely defined quasi-acyclic automata with 3 inputs, n transient and k absorbing labeled states.

Original entry on oeis.org

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

Offset: 0

Valery A. Liskovets, Apr 09 2003

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

The first column is A082158.

			The array begins:
            1,              1,               1,             1, ...;
            1,              8,              27,            64, ...;
           15,            368,            2727,         11904, ...;
         1024,          53672,          710532,       4975936, ...;
       198581,       18417792,       386023509,    3977848832, ...;
     85102056,    12448430408,    381535651512, 5451751738944, ...;
  68999174203, 14734002979456, 624245820664563, ...;
Antidiagonals begin as:
  1;
  1,   1;
  1,   8,    15;
  1,  27,   368,    1024;
  1,  64,  2727,   53672,    198581;
  1, 125, 11904,  710532,  18417792,    85102056;
  1, 216, 38375, 4975936, 386023509, 12448430408, 68999174203;

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. A082158, A082162, A082169.

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

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

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

A102916 Triangle, read by rows, where the antidiagonals are formed by interleaving the rows of triangle A102098 with the rows of its matrix square (A102920).

Original entry on oeis.org

1, 1, 2, 1, 4, 3, 3, 8, 9, 4, 7, 40, 27, 16, 5, 36, 152, 189, 64, 25, 6, 139, 1128, 999, 576, 125, 36, 7, 1036, 6200, 9720, 3904, 1375, 216, 49, 8, 5711, 61120, 69687, 47040, 11375, 2808, 343, 64, 9, 56355, 442552, 857466, 416704, 163500, 27432, 5145, 512

Offset: 0

Paul D. Hanna, Jan 21 2005

Column 0 is A102917, the interleaving of A082162 with A102921. Under matrix cube, triangle A102098 shifts each column up 1 row.

			Rows begin:
[1],
[1,2],
[1,4,3],
[3,8,9,4],
[7,40,27,16,5],
[36,152,189,64,25,6],
[139,1128,999,576,125,36,7],
[1036,6200,9720,3904,1375,216,49,8],
[5711,61120,69687,47040,11375,2808,343,64,9],...
The antidiagonals are formed by interleaving the
rows of triangle A102098:
[1],
[1,2],
[7,8,3],
[139,152,27,4],...
with the rows of the matrix square of A102098,
which is triangle A102920:
[1],
[3,4],
[36,40,9],
[1036,1128,189,16],...
G.f. for Column 0 (A102917): 1 = 1*(1-x) + 1*x*(1-x)
+ 1*x^2*(1-x)(1-2x) + 3*x^3*(1-x)(1-2x)
+ 7*x^4*(1-x)(1-2x)(1-3x) + 36*x^5*(1-x)(1-2x)(1-3x) +...
+ A082162(n)*x^(2n)*(1-x)(1-2x)*..*(1-(n+1)x)
+ A102921(n)*x^(2n+1)*(1-x)(1-2x)*..*(1-(n+1)x) + ...
G.f. for Column 1 (A102918): 2 = 2*(1-2x) + 4*x*(1-2x)
+ 8*x^2*(1-2x)(1-3x) + 40*x^3*(1-2x)(1-3x)
+ 152*x^4*(1-2x)(1-3x)(1-4x) + 1128*x^5*(1-2x)(1-3x)(1-4x) +...
+ T(2n+1,1)*x^(2n)*(1-2x)(1-3x)*..*(1-(n+2)x)
+ T(2n+2,1)*x^(2n+1)*(1-2x)(1-3x)*..*(1-(n+2)x) + ...

Cf. A102086, A102098, A102920, A102917, A102918.

PARI
```
{T(n,k)=if(n
				
```

G.f. for column k: T(k, k) = k+1 = Sum_{n>=0} T(n+k, k)*x^n*Product_{j=k..[n/2+k]} (1-(j+1)*x).

A102099 Column 1 of triangular matrix A102098, which shifts upward to exclude the main diagonal under matrix cube.

Original entry on oeis.org

0, 2, 8, 152, 6200, 442552, 49399320, 8003532512, 1784040237288, 525504809786112, 198213959637435608, 93352856625931514024, 53776417402985961020144, 37244016639064540041311632

Offset: 0

Paul D. Hanna, Dec 29 2004

nonn

Column 0 of A102098 is A082162.

Cf. A102098, A082162, A102100.

{a(n)=local(A=matrix(2,2),B);A[1,1]=1; for(m=2,n+1,B=matrix(m,m);for(i=1,m, for(j=1,i, if(j==i,B[i,j]=j,if(j==1,B[i,j]=(A^3)[i-1,1], B[i,j]=(A^3)[i-1,j]));));A=B); return(A[n+1,2])}

A102101 Triangular matrix, read by rows, that satisfies: T(n,k) = [T^4](n-1,k) when n>k>=0, with T(n,n) = (n+1).

Original entry on oeis.org

1, 1, 2, 15, 16, 3, 1000, 1040, 81, 4, 189035, 196080, 14175, 256, 5, 79278446, 82196224, 5866992, 94464, 625, 6, 63263422646, 65585046960, 4667640795, 73281280, 419375, 1296, 7, 86493299281972, 89664824687968, 6376139907030

Offset: 0

Paul D. Hanna, Dec 29 2004

Column 0 forms A102102. Column 1 forms A102103. Row sums form A102104. This triangle is a variant of A102086 and A102098.

			Rows of T begin:
[1],
[1,2],
[15,16,3],
[1000,1040,81,4],
[189035,196080,14175,256,5],
[79278446,82196224,5866992,94464,625,6],
[63263422646,65585046960,4667640795,73281280,419375,1296,7].
Matrix fourth power T^4 equals T excluding the main diagonal:
[1],
[15,16],
[1000,1040,81],
[189035,196080,14175,256],
[79278446,82196224,5866992,94464,625],...

Cf. A102102, A102103, A102104, A102086, A102098.

{T(n,k)=local(A=matrix(1,1),B);A[1,1]=1; for(m=2,n+1,B=matrix(m,m);for(i=1,m, for(j=1,i, if(j==i,B[i,j]=j,if(j==1,B[i,j]=(A^4)[i-1,1], B[i,j]=(A^4)[i-1,j]));));A=B);return(A[n+1,k+1])}

T(n, 0) = A082162(n) for n>0, with T(0, 0) = 1.

A102917 Column 0 of triangle A102916.

Original entry on oeis.org

1, 1, 1, 3, 7, 36, 139, 1036, 5711, 56355, 408354, 5045370, 45605881, 679409158, 7390305396, 129195427716, 1647470410551, 33114233390505, 485292763088275, 11038606786054201, 183049273155939442, 4652371578279864792

Offset: 0

Paul D. Hanna, Jan 21 2005

nonn

Also equals the interleaving of A082162 with A102921, which equal column 0 of triangle A102098 and its matrix square (A102920), respectively.

			1 = 1*(1-x) + 1*x*(1-x) + 1*x^2*(1-x)(1-2x) + 3*x^3*(1-x)(1-2x)
+ 7*x^4*(1-x)(1-2x)(1-3x) + 36*x^5*(1-x)(1-2x)(1-3x)
+ 139*x^6*(1-x)(1-2x)(1-3x)(1-4x) + 1036*x^7*(1-x)(1-2x)(1-3x)(1-4x) + ...
+ A082162(n)*x^(2n)*(1-x)(1-2x)*..*(1-(n+1)x)
+ A102921(n)*x^(2n+1)*(1-x)(1-2x)*..*(1-(n+1)x) + ...

Cf. A102916, A082162, A102921, A102098, A102920.

{a(n)=if(n==0,1,polcoeff(1-sum(k=0,n-1,a(k)*x^k*prod(j=1,k\2+1,1-j*x+x*O(x^n))),n))}

G.f.: 1 = Sum_{n>=0}(a(2*n)+a(2*n+1)*x)*x^(2*n)*Product_{k=1..n+1}(1-k*x) where a(2*n)=A082162(n) and a(2*n+1)=A102921(n).

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

A102102 Column 0 of triangular matrix A102101, which shifts upward to exclude the main diagonal under matrix fourth power.

Original entry on oeis.org

1, 1, 15, 1000, 189035, 79278446, 63263422646, 86493299281972, 187766975052827491, 611024291011881918991, 2849262494779035461688236, 18362167739517547774072439880, 158759599858376078627687256207242

Offset: 0

Paul D. Hanna, Dec 29 2004

nonn

Analogous to A082161 and A082162, this describes the deterministic completely defined initially connected acyclic automata with 4 inputs and n transient unlabeled states (and a unique absorbing state) with a(0)=1.

Manosij Ghosh Dastidar and Michael Wallner, Asymptotics of relaxed k-ary trees, arXiv:2404.08415 [math.CO], 2024. See p. 1.4.

Cf. A102101, A082161, A082162.

{a(n)=local(A=matrix(1,1),B);A[1,1]=1; for(m=2,n+1,B=matrix(m,m);for(i=1,m, for(j=1,i, if(j==i,B[i,j]=j,if(j==1,B[i,j]=(A^4)[i-1,1], B[i,j]=(A^4)[i-1,j]));));A=B);return(A[n+1,1])}

A102400 Triangle, read by rows, where T(n,k) = Sum_{j=0..k} T(n-1,j)(j+1)[(k+1)(k+2)/2 - j(j+1)/2] for n>k>0, with T(0,0)=1 and T(n,n) = T(n,n-1) for n>0.

Original entry on oeis.org

1, 1, 1, 1, 7, 7, 1, 31, 139, 139, 1, 127, 1567, 5711, 5711, 1, 511, 15379, 126579, 408354, 408354, 1, 2047, 143527, 2357431, 15333661, 45605881, 45605881, 1, 8191, 1312219, 40769819, 473433344, 2634441290, 7390305396, 7390305396, 1, 32767

Offset: 0

Paul D. Hanna, Jan 06 2005

Main diagonal is A082162 (with offset). This sequence is derived from column 0 of A102098.

			T(4,2) = 1567 = 1*6 + 31*10 + 139*9
= T(3,0)*R(0,2) + T(3,1)*R(1,2) + T(3,2)*R(2,2).
Rows begin:
[1],
[1,1],
[1,7,7],
[1,31,139,139],
[1,127,1567,5711,5711],
[1,511,15379,126579,408354,408354],
[1,2047,143527,2357431,15333661,45605881,45605881],...
where the transpose of the recurrence coefficients given by
[R^t](n,k) = (k+1)*((n+1)*(n+2)/2 - k*(k+1)/2) form triangle:
[1],
[3,4],
[6,10,9],
[10,18,21,16],
[15,28,36,36,25],...
which equals the matrix square of the triangle:
[1],
[1,2],
[1,2,3],
[1,2,3,4],
[1,2,3,4,5],...

Cf. A082162, A102098, A102317.

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

PARI
```
{T(n,k)=if(n
				
```

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

A102098 Triangular matrix, read by rows, that satisfies: T(n,k) = [T^3](n-1,k) when n>k>=0, with T(n,n) = (n+1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A082170 Deterministic completely defined 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

A102916 Triangle, read by rows, where the antidiagonals are formed by interleaving the rows of triangle A102098 with the rows of its matrix square (A102920).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A102099 Column 1 of triangular matrix A102098, which shifts upward to exclude the main diagonal under matrix cube.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A102101 Triangular matrix, read by rows, that satisfies: T(n,k) = [T^4](n-1,k) when n>k>=0, with T(n,n) = (n+1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A102917 Column 0 of triangle A102916.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

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

A102102 Column 0 of triangular matrix A102101, which shifts upward to exclude the main diagonal under matrix fourth power.

Views

Author

Keywords

Comments

Links

Crossrefs

A102400 Triangle, read by rows, where T(n,k) = Sum_{j=0..k} T(n-1,j)(j+1)[(k+1)(k+2)/2 - j(j+1)/2] for n>k>0, with T(0,0)=1 and T(n,n) = T(n,n-1) for n>0.