|
|
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
|
|
|
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.
|
|
KEYWORD
|
hard,nonn
|
|
AUTHOR
|
|
|
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
|
|
|
|