login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A082169 Deterministic completely defined quasi-acyclic automata with 2 inputs, n transient and k absorbing labeled states. 6
1, 1, 1, 1, 4, 7, 1, 9, 56, 142, 1, 16, 207, 1780, 5941, 1, 25, 544, 9342, 103392, 428856, 1, 36, 1175, 32848, 709893, 9649124, 47885899, 1, 49, 2232, 91150, 3142528, 82305144, 1329514816, 7685040448, 1, 64, 3871, 215892, 10682325, 440535696, 13598786979, 254821480596, 1681740027657 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
0,5
COMMENTS
Array read by antidiagonals: (0,1),(0,2),(1,1),(0,3),...
The first column is A082157.
LINKS
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) = T_2(n, k) where T_2(0, k) = 1, T_2(n, k) = Sum_{i=0..n-1} (-1)^(n-i-1)*binomial(n, i)*(i+k)^(2*(n-i))*T_2(i, k), n > 0.
EXAMPLE
The array begins:
1, 1, 1, 1, 1, ...;
1, 4, 9, 16, 25, ...;
7, 56, 207, 544, 1175, ...;
142, 1780, 9342, 32848, 91150, ...;
5941, 103392, 709893, 3142528, 10682325, ...;
428856, 9649124, 82305144, 440535696, 1775027000, ...;
47885899, 1329514816, 13598786979, 85529171200, ...;
Antidiagonal triangle begins as:
1;
1, 1;
1, 4, 7;
1, 9, 56, 142;
1, 16, 207, 1780, 5941;
1, 25, 544, 9342, 103392, 428856;
1, 36, 1175, 32848, 709893, 9649124, 47885899;
1, 49, 2232, 91150, 3142528, 82305144, 1329514816, 7685040448;
MATHEMATICA
T[0, _]= 1; T[n_, k_]:= T[n, k]= Sum[Binomial[n, i] (-1)^(n-i-1)*(i + k)^(2n-2i) 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
(Magma)
function A(n, k)
if n eq 0 then return 1;
else return (&+[(-1)^(n-j+1)*Binomial(n, j)*(k+j)^(2*n-2*j)*A(j, k): j in [0..n-1]]);
end if;
end function;
A082169:= func< n, k | A(k, n-k+1) >;
[A082169(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)^(2*n-2*j)*A(j, k) for j in range(n))
def A082169(n, k): return A(k, n-k+1)
flatten([[A082169(n, k) for k in range(n+1)] for n in range(12)]) # G. C. Greubel, Jan 19 2024
CROSSREFS
Sequence in context: A019670 A093436 A343805 * A209634 A340584 A289523
KEYWORD
easy,nonn,tabl
AUTHOR
Valery A. Liskovets, Apr 09 2003
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 17 12:12 EDT 2024. Contains 371763 sequences. (Running on oeis4.)