login
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
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
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: A152422 A332133 A256460 * A285628 A319886 A021736
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