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,3

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]

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.

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.

Example

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

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

Prog

(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
(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
(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

Crossrefs

Cf. A082159, A082163, A082169.

Sequence in context: A049967 A221780 A221723 * A164795 A201741 A280192

Adjacent sequences: A082168 A082169 A082170 * A082172 A082173 A082174

Keyword

easy,nonn,tabl

Author

Valery A. Liskovets, Apr 09 2003

Extensions

Name clarified by Petros Hadjicostas, Mar 07 2021

Status

approved