This site is supported by donations to The OEIS Foundation.

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 Prateek Karandikar and Philippe Schnoebelen, On the index of Simon's congruence for piecewise testability, arXiv:1310.1278 [cs.FL], 2013-2014. 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 Sequence in context: A006319 A202020 A059606 * A231297 A231358 A000303 Adjacent sequences:  A228947 A228948 A228949 * A228951 A228952 A228953 KEYWORD nonn,more AUTHOR Prateek Karandikar and Philippe Schnoebelen, Oct 09 2013 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.