

A228950


The index of Simon's piecewise testability congruence, for words of length n over a 2letter alphabet.


0



1, 4, 16, 68, 312, 1560, 8528, 50864, 329248, 2298592, 17203264, 137289920
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Consider an alphabet with two letters, say {0,1}. For two words v and w over this alphabet, we say v embeds in w, or v is a subsequence of w, if v can be obtained from w by erasing some (occurrences of) letters.
For a natural number n, define two words to be nequivalent if they have the same subsequences of length up to n. The nth term of this sequence is the number of equivalence classes of this equivalence relation.


LINKS



EXAMPLE

For n=1, here are representatives of each of the four equivalence classes (taking the alphabet to be {0,1}) : empty word, 0, 1, 01.


CROSSREFS



KEYWORD

nonn,more


AUTHOR



STATUS

approved



