A248905 Array read by antidiagonals: the number of automata over an n-letter alphabet whose states are determined by the last k symbols read.

1, 1, 2, 1, 5, 5, 1, 30, 192, 15, 1, 1247

Offset

1,3

Comments

T(n,k) is the number of automata over an n-letter alphabet whose states are determined by the last k symbols read. These therefore correspond to a count of a special class of synchronized automata as in the Road Coloring Problem solved by Trahtman.

Also, T(n,k) counts equivalence relations on de Bruijn graphs compatible with edge labels.

Links

Table of n, a(n) for n=1..12.

Collin Bleak, Table of a(n,k) listed as antidiagonal ordered sequence in index m = 1..15.

Collin Bleak, Peter J. Cameron, and Feyishayo Olukoya, Automorphisms of shift spaces and the Higman-Thomspon groups: the one-sided case, arXiv:2004.08478 [math.GR], 2020.

Avraham N. Trahtman, The Road Coloring Problem, arXiv:0709.0099 [cs.DM], 2007.

Avraham N. Trahtman, The Road Coloring Problem, Israel Journal of Mathematics, 172 (2009), 51-60.

Formula

T(n,1) = A000110(n).

Example

Below is the table T(n,k) for row n = alphabet size, and column k = synchronizing word length. Top left entry is T(1,1).
1   1     1      1      1     1   ...
2   5     30     1247   ?
5   192   ?      ?
15  98721 ?
203 ?
.
.
.

Crossrefs

Cf. A000110 (first column).

Sequence in context: A270250 A204119 A046757 * A118244 A108410 A058116

Adjacent sequences: A248902 A248903 A248904 * A248906 A248907 A248908

Keyword

hard,more,nonn,tabl

Author

Collin Bleak and Peter J. Cameron, Mar 06 2015

Status

approved