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

Comments

Array read by antidiagonals: (0,1),(0,2),(1,1),(0,3),... . The first column is A082160.

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

Example

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;

Mathematica

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

Prog

(Magma)
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
(SageMath)
@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

Crossrefs

Cf. A082160, A082164, A082170, A082171.

Sequence in context: A147385 A147347 A183109 * A053288 A282917 A050301

Adjacent sequences: A082169 A082170 A082171 * A082173 A082174 A082175

Keyword

easy,nonn,tabl

Author

Valery A. Liskovets, Apr 09 2003

Status

approved