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

Author

Valery A. Liskovets, Apr 09 2003

Keywords

• easy
• nonn
• tabl

Comments

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]

Examples

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

Links

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

Crossrefs

Cf. A082159, A082163, A082169.

Programs

Magma

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

Mathematica

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

PARI

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

SageMath

@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

Formula

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.

Extensions

Name clarified by Petros Hadjicostas, Mar 07 2021