A082163 -id:A082163 - cp's OEIS frontend

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).

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

A103236 Triangular matrix T, read by rows, that satisfies: T^2 + 2T = SHIFTUP(T), also T^(n+1) + 2T^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, 3, 2, 15, 8, 3, 114, 56, 15, 4, 1191, 568, 135, 24, 5, 15993, 7536, 1710, 264, 35, 6, 263976, 123704, 27495, 4008, 455, 48, 7, 5189778, 2425320, 533565, 75696, 8050, 720, 63, 8, 118729335, 55403008, 12121920, 1695528, 174615, 14544, 1071, 80, 9

Offset: 0

Paul D. Hanna, Jan 31 2005

Leftmost column is A082163 (enumerates acyclic automata with 2 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],
[3,2],
[15,8,3],
[114,56,15,4],
[1191,568,135,24,5],
[15993,7536,1710,264,35,6],
[263976,123704,27495,4008,455,48,7],
[5189778,2425320,533565,75696,8050,720,63,8],...
Rows of T^2 begin:
[1],
[9,4],
[84,40,9],
[963,456,105,16],
[13611,6400,1440,216,25],...
Rows of T^2+2*T equals SHIFTUP(T):
[3],
[15,8],
[114,56,15],
[1191,568,135,24],
[15993,7536,1710,264,35],...
G.f. for column 0: 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) + ... + T(n,0)*x^n/(1-2*x)^n*(1-3x)(1-4x)*..*(1-(n+3)x) + ...
G.f. for column 1: 2 = 2*(1-4x) + 8*x/(1-2x)*(1-4x)(1-5x) + 56*x^2/(1-2x)^2*(1-4x)(1-5x)(1-6x) + 568*x^3/(1-2x)^3*(1-4x)(1-5x)(1-6x)(1-7x) + ... + T(n,1)*x^(n-1)/(1-2*x)^(n-1)*(1-4x)(1-5x)*..*(1-(n+3)x) + ...

Cf. A082163, A103247, A103242.

PARI
```
{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-2*x)^(n-k) * Product_{j=0..n-k} (1-(j+k+3)*x). Diagonalization: T = P*D*P^-1 where P(r, c) = A103247(r, c)/(r-c)! = (-1)^(r-c)*(c^2+2*c)^(r-c)/(r-c)! for r>=c>=1 and [P^-1](r, c) = A103242(r, c)/(r-c)! and D is a diagonal matrix = {1, 2, 3, ...}.

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

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

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

A103236 Triangular matrix T, read by rows, that satisfies: T^2 + 2*T = SHIFTUP(T), also T^(n+1) + 2*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

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

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

A103236 Triangular matrix T, read by rows, that satisfies: T^2 + 2T = SHIFTUP(T), also T^(n+1) + 2T^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,...}.