A152139 Correlation classes of pairs of different words.

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

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: A152422 A332133 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