login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 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 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, 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), 51-60.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 11 17:57 EDT 2020. Contains 335626 sequences. (Running on oeis4.)