login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A152139 Correlation classes of pairs of different words. 2

%I #17 Mar 13 2014 01:15:54

%S 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,

%T 141,141,141,141,141,0,193,322,324,324,324,324,324,324,324,324,324,0,

%U 415,655,657,657,657,657,657,657,657,657,657,657,657,0,839,1322,1329

%N Correlation classes of pairs of different words.

%C Let b(m,q) be the number of correlation classes of pairs of different q-ary words of length m.

%C Then a(m*(m-1)+q) = b(m,q), for q from 1 to 2*m.

%C 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].

%C The equivalence relation is given by equivalence under transpose of the matrix and equivalence under exchange of X and Y.

%C Rahmann and Rivals [Section 3.3] call the equivalence classes "types of correlation matrices".

%C Trivially, b(m,q) = b(m,2*m) for q > 2*m.

%C Given the first terms of the sequence above, an obvious conjecture is that b(m,q) = b(m,4) for all q > 4.

%C 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

%H P. Leopardi, <a href="/A152139/b152139.txt">Table of n, a(n) for n=1..115</a>

%H Leo J. Guibas and Andrew M. Odlyzko, <a href="http://dx.doi.org/10.1016/0097-3165(81)90005-4">String overlaps, pattern matching and nontransitive games</a>, Journal of Combinatorial Theory Series A, 30 (1981), 183-208.

%H Sven Rahmann and Eric Rivals, <a href="http://dx.doi.org/10.1017/S0963548302005473">On the distribution of the number of missing words in random texts</a>, Combinatorics, Probability and Computing (2003) 12, 73-87.

%H Andrew L. Rukhin, <a href="http://www.jstor.org/stable/1428322">Distribution of the number of words with a prescribed frequency and tests of randomness</a>, Advances in Probability, Vol. 34, No. 4, (Dec 2002), 775-797.

%F 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.

%F 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.

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

%Y Cf. A005434, which treats autocorrelations.

%K hard,nonn

%O 1,4

%A _Paul Leopardi_, Nov 26 2008

%E 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

%E 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).

%E 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

%E Calculated b(14,2)=23759, b(14,3)=35286. - _Paul Leopardi_, Dec 07 2013

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 15:28 EDT 2024. Contains 371254 sequences. (Running on oeis4.)