1,4

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. [From Paul C. Leopardi (paul.leopardi(AT)anu.edu.au), Jun 14 2009]

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.

P. Leopardi, Table of n, a(n) for n=1..95

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.

Rahmann and Rivals [Table 1] have b(2,q) = 6 for q >= 4.

Cf. A005434, which treats autocorrelations

Sequence in context: A144253 A138743 A152422 this_sequence A021736 A091478 A086727

Adjacent sequences: A152136 A152137 A152138 this_sequence A152140 A152141 A152142

hard,nonn

Paul C. Leopardi (paul.leopardi(AT)anu.edu.au), Nov 26 2008

Calculated b(8,q) for q from 5 to 16, and b(9,q) for q from 1 to 8. Paul C. Leopardi (paul.leopardi(AT)anu.edu.au), Jun 14 2009