A082164 -id:A082164 - cp's OEIS frontend

A082172 A subclass of quasi-acyclic automata with 3 inputs, n transient and k absorbing labeled states.

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.

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, ...}.

cp's OEIS Frontend

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