A259482 - OEIS

A259482

Number of states in smallest deterministic finite automaton that accepts exactly the strings over the alphabet {1,2,...,n} having all permutations of 12...n as subsequences.

2, 6, 44, 2014, 1651377

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

The automaton is assumed to be "complete"; that is, there is a transition from every state on every letter.

Also, the length of the shortest string accepted by this automaton is the sequence A062714.

LINKS

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

Kevin Ryde, Perl program running Foma or SFST to construct the DFAs

EXAMPLE

For n = 2 there is a 6-state automaton accepting (11*22*1 + 22*11*2)(1 + 2)*.

CROSSREFS

Cf. A062714.

Sequence in context: A171690 A259763 A219337 * A332757 A255015 A347984

Adjacent sequences: A259479 A259480 A259481 * A259483 A259484 A259485

KEYWORD

nonn,hard,more,nice

AUTHOR

Jeffrey Shallit, Jun 28 2015

EXTENSIONS

a(5) from Kevin Ryde, Aug 21 2020

STATUS

approved