|
| |
|
|
A228950
|
|
The index of Simon's piecewise testability congruence, for words of length n over a 2-letter 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 n-equivalent if they have the same subsequences of length up to n. The n-th 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
|
| |
|
|
