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

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A229954 The index of Simon's piecewise testability congruence, for words of length 2 over a n-letter alphabet. 0
3, 16, 152, 2326, 52132, 1602420, 64529264 (list; graph; refs; listen; history; text; internal format)



Consider an alphabet with n letters, say {a_0, a_1, ... a_{n-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.

Define two words to be 2-equivalent if they have the same subsequences of length up to 2. The n-th term of this sequence is the number of equivalence classes of this equivalence relation, when the size of the alphabet is n.


Table of n, a(n) for n=1..7.

Prateek Karandikar and Philippe Schnoebelen, On the index of Simon's congruence for piecewise testability arXiv:1310.1278 [cs.FL], 2013-2014.


For n=1, with the alphabet {a_0}, representatives of the three equivalence classes are : empty word, a_0, a_0a_0.


Sequence in context: A217251 A125281 A086371 * A228513 A135753 A191959

Adjacent sequences:  A229951 A229952 A229953 * A229955 A229956 A229957




Prateek Karandikar and Philippe Schnoebelen, Oct 09 2013



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.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 26 09:12 EDT 2017. Contains 287093 sequences.