

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 qary words of length m.
Then a(m*(m1)+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), 183208.
Sven Rahmann and Eric Rivals, On the distribution of the number of missing words in random texts, Combinatorics, Probability and Computing (2003) 12, 7387.
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), 775797.


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 * A021736 A091478 A239567
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 bfile).
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



