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

Offset: 1

Author

Jeffrey Shallit, Jun 28 2015

Keywords

• nonn
• hard
• more
• nice

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.

Examples

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

Links

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

Crossrefs

Cf. A062714.

Extensions

a(5) from Kevin Ryde, Aug 21 2020