

A248905


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


1



1, 1, 2, 1, 5, 5, 1, 30, 192, 15, 1, 1247
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

a(n,k) is the number of automata over an nletter 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, a(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.
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), 5160.


FORMULA

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


EXAMPLE

Below is the table a(n,k) for row n = alphabet size, and column k = synchronizing word length. Top left entry is a(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



