Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #35 Aug 04 2020 06:18:45
%S 1,1,2,1,5,5,1,30,192,15,1,1247
%N Array read by antidiagonals: the number of automata over an n-letter alphabet whose states are determined by the last k symbols read.
%C 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.
%C Also, T(n,k) counts equivalence relations on de Bruijn graphs compatible with edge labels.
%H Collin Bleak, <a href="/A248905/a248905.txt">Table of a(n,k) listed as antidiagonal ordered sequence in index m = 1..15.</a>
%H Collin Bleak, Peter J. Cameron, and Feyishayo Olukoya, <a href="https://arxiv.org/abs/2004.08478">Automorphisms of shift spaces and the Higman-Thomspon groups: the one-sided case</a>, arXiv:2004.08478 [math.GR], 2020.
%H Avraham N. Trahtman, <a href="http://arxiv.org/abs/0709.0099">The Road Coloring Problem</a>, arXiv:0709.0099 [cs.DM], 2007.
%H Avraham N. Trahtman, <a href="http://dx.doi.org/10.1007/s11856-009-0062-5">The Road Coloring Problem</a>, Israel Journal of Mathematics, 172 (2009), 51-60.
%F T(n,1) = A000110(n).
%e 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).
%e 1 1 1 1 1 1 ...
%e 2 5 30 1247 ?
%e 5 192 ? ?
%e 15 98721 ?
%e 203 ?
%e .
%e .
%e .
%Y Cf. A000110 (first column).
%K hard,more,nonn,tabl
%O 1,3
%A _Collin Bleak_ and _Peter J. Cameron_, Mar 06 2015