1,2

Let b(m,q) be the number of correlation classes of pairs of different q-ary words of length m, as per the definition of sequence A152139. Then here a(m)=b(m,4), the number of correlation classes of pairs of different words of length m in an alphabet of size 4. In other words, for m>1, a(m)=c(m*(m-1)+4), where c is given by A152139. A conjecture mentioned in the comments to A152139 translates here to b(m,q) = a(m) for all q > 4. For more details, see the comments to A152139.

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.

Rahmann and Rivals [Table 1] has a(2)=6.

Cf. A152139. See also A005434, which treats autocorrelations.

Sequence in context: A027993 A028492 A059822 this_sequence A109903 A014480 A048778

Adjacent sequences: A152956 A152957 A152958 this_sequence A152960 A152961 A152962

hard,nonn

Paul C. Leopardi (paul.leopardi(AT)anu.edu.au), Dec 15 2008, Dec 28 2008