The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A152139 Correlation classes of pairs of different words. 2
 0, 1, 0, 3, 6, 6, 0, 11, 20, 20, 20, 20, 0, 31, 54, 55, 55, 55, 55, 55, 0, 87, 141, 141, 141, 141, 141, 141, 141, 141, 0, 193, 322, 324, 324, 324, 324, 324, 324, 324, 324, 324, 0, 415, 655, 657, 657, 657, 657, 657, 657, 657, 657, 657, 657, 657, 0, 839, 1322, 1329 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS Let b(m,q) be the number of correlation classes of pairs of different q-ary words of length m. Then a(m*(m-1)+q) = b(m,q), for q from 1 to 2*m. A correlation class for a pair of different words is defined as an equivalence class of 2*2 correlation matrices, M=[XX XY; YX YY], where X and Y are different words of length m in an alphabet of size q, and the correlations XX, XY, YX, YY are binary words of length m as defined by Guibas and Odlyzko [Section 1]. The equivalence relation is given by equivalence under transpose of the matrix and equivalence under exchange of X and Y. Rahmann and Rivals [Section 3.3] call the equivalence classes "types of correlation matrices". Trivially, b(m,q) = b(m,2*m) for q > 2*m. Given the first terms of the sequence above, an obvious conjecture is that b(m,q) = b(m,4) for all q > 4. Conjecture that b(m,q) = b(m,4) for all q > 4, is now verified for m to and including 8. Also b(9,q)=b(9,4) for q=5,6,7,8 at least. - Paul Leopardi, Jun 14 2009 LINKS P. Leopardi, Table of n, a(n) for n=1..115 Leo J. Guibas and Andrew M. Odlyzko, String overlaps, pattern matching and nontransitive games, Journal of Combinatorial Theory Series A, 30 (1981), 183-208. Sven Rahmann and Eric Rivals, On the distribution of the number of missing words in random texts, Combinatorics, Probability and Computing (2003) 12, 73-87. Andrew L. Rukhin, Distribution of the number of words with a prescribed frequency and tests of randomness, Advances in Probability, Vol. 34, No. 4, (Dec 2002), 775-797. FORMULA See the generating function for the "absence probability of both P and Q in a text of length m" given in Lemma 3.2 of Rahmann and Rivals. This generating function uses the polynomial form of the correlation matrix and for a given length m and alphabet size q, each correlation class yields a distinct generating function. EXAMPLE Rahmann and Rivals [Table 1] have b(2,q) = 6 for q >= 4. CROSSREFS Cf. A005434, which treats autocorrelations. Sequence in context: A138743 A152422 A256460 * A285628 A319886 A021736 Adjacent sequences:  A152136 A152137 A152138 * A152140 A152141 A152142 KEYWORD hard,nonn AUTHOR Paul Leopardi, Nov 26 2008 EXTENSIONS Calculated b(8,q) for q from 5 to 16, and b(9,q) for q from 1 to 8. - Paul Leopardi, Jun 14 2009 Calculated b(9,q) for q from 9 to 18, b(10,q) for q from 1 to 20, b(11,q) for q from 1 to 5 (see b-file). Also calculated b(12,2)=8747, b(12,3)=13182, b(12,4)=13221, b(13,2)=14425, b(13,3)=21252. - Paul Leopardi, Apr 20 2010 Calculated b(14,2)=23759, b(14,3)=35286. - Paul Leopardi, Dec 07 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 9 01:33 EDT 2020. Contains 333339 sequences. (Running on oeis4.)