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

Author

Collin Bleak and Peter J. Cameron, Mar 06 2015

Keywords

• hard
• more
• nonn
• tabl

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.

Examples

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

Links

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

Crossrefs

Cf. A000110 (first column).

Formula

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