|
%I #45 Apr 15 2015 05:27:15
%S 1,4,16,68,312,1560,8528,50864,329248,2298592,17203264,137289920
%N The index of Simon's piecewise testability congruence, for words of length n over a 2-letter alphabet.
%C 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.
%C 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.
%H Prateek Karandikar and Philippe Schnoebelen, <a href="http://arxiv.org/abs/1310.1278">On the index of Simon's congruence for piecewise testability</a>, arXiv:1310.1278 [cs.FL], 2013-2014.
%e 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.
%K nonn,more
%O 0,2
%A _Prateek Karandikar_ and _Philippe Schnoebelen_, Oct 09 2013
|
