A082162
Number of deterministic completely defined initially connected acyclic automata with 3 inputs and n transient unlabeled states (and a unique absorbing state).
Original entry on oeis.org
1, 7, 139, 5711, 408354, 45605881, 7390305396, 1647470410551, 485292763088275, 183049273155939442, 86211400693272461866
Offset: 1
- R. Bacher, C. Reutenauer, The number of right ideals of given codimension over a finite field, in Noncommutative Birational Geometry, Representations and Combinatorics, edited by Arkady. Berenstein and Vladimir. Retakha, Contemporary Mathematics, Vol. 592, 2013.
- Vaclav Kotesovec (after Jean-François Alcover), Table of n, a(n) for n = 1..210
- Manosij Ghosh Dastidar and Michael Wallner, Asymptotics of relaxed k-ary trees, arXiv:2404.08415 [math.CO], 2024. See p. 1.4.
- 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.
A082160
Deterministic completely defined acyclic automata with 3 inputs and n+1 transient labeled states including a unique state having all transitions to the absorbing state.
Original entry on oeis.org
1, 7, 315, 45682, 15646589, 10567689552, 12503979423607, 23841011541867520, 68835375121428936153, 286850872894190847235840, 1660638682341609286358474579, 12947089879912710544534553836032
Offset: 0
- G. C. Greubel, Table of n, a(n) for n = 0..150
- 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.
-
function a(n) // a = A082160
if n eq 0 then return 1;
else return (&+[Binomial(n,j)*(-1)^(n-j-1)*((j+2)^3 - 1)^(n-j)*a(j): j in [0..n-1]]);
end if;
end function;
[a(n): n in [0..20]]; // G. C. Greubel, Jan 17 2024
-
a[0] = 1; a[n_] := a[n] = Sum[Binomial[n, i] (-1)^(n - i - 1) ((i + 2)^3 - 1)^(n - i) a[i], {i, 0, n - 1}];
Table[a[n], {n, 0, 11}] (* Jean-François Alcover, Aug 29 2019 *)
-
@CachedFunction
def a(n): # A082160
if n==0: return 1
else: return sum(binomial(n,j)*(-1)^(n-j-1)*((j+2)^3 -1)^(n-j)*a(j) for j in range(n))
[a(n) for n in range(21)] # G. C. Greubel, Jan 17 2024
A082170
Deterministic completely defined quasi-acyclic automata with 3 inputs, n transient and k absorbing labeled states.
Original entry on oeis.org
1, 1, 1, 1, 8, 15, 1, 27, 368, 1024, 1, 64, 2727, 53672, 198581, 1, 125, 11904, 710532, 18417792, 85102056, 1, 216, 38375, 4975936, 386023509, 12448430408, 68999174203, 1, 343, 101520, 23945000, 3977848832, 381535651512, 14734002979456, 95264160938080
Offset: 0
The array begins:
1, 1, 1, 1, ...;
1, 8, 27, 64, ...;
15, 368, 2727, 11904, ...;
1024, 53672, 710532, 4975936, ...;
198581, 18417792, 386023509, 3977848832, ...;
85102056, 12448430408, 381535651512, 5451751738944, ...;
68999174203, 14734002979456, 624245820664563, ...;
Antidiagonals begin as:
1;
1, 1;
1, 8, 15;
1, 27, 368, 1024;
1, 64, 2727, 53672, 198581;
1, 125, 11904, 710532, 18417792, 85102056;
1, 216, 38375, 4975936, 386023509, 12448430408, 68999174203;
- 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.
-
function A(n,k)
if n eq 0 then return 1;
else return (&+[(-1)^(n-j+1)*Binomial(n,j)*(k+j)^(3*n-3*j)*A(j,k): j in [0..n-1]]);
end if;
end function;
A082170:= func< n,k | A(k,n-k+1) >;
[A082170(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)^(3n-3i) T[i, k], {i,0,n-1}];
Table[T[n-k-1, k], {n, 1, 9}, {k, n-1, 1, -1}]//Flatten (* Jean-François Alcover, Aug 29 2019 *)
-
@CachedFunction
def A(n,k):
if n==0: return 1
else: return sum((-1)^(n-j+1)*binomial(n,j)*(k+j)^(3*n-3*j)*A(j,k) for j in range(n))
def A082170(n,k): return A(k,n-k+1)
flatten([[A082170(n,k) for k in range(n+1)] for n in range(12)]) # G. C. Greubel, Jan 19 2024
Showing 1-3 of 3 results.
Comments