login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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: A138743 A152422 A256460 * A285628 A021736 A091478

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 24 18:18 EDT 2017. Contains 286997 sequences.