login
Number of correlation classes for pairs of different words in an alphabet of size 4.
0

%I #9 Dec 18 2016 12:48:39

%S 1,6,20,55,141,324,657,1329,2515,4592,7897,13221

%N Number of correlation classes for pairs of different words in an alphabet of size 4.

%C Let b(m,q) be the number of correlation classes of pairs of different q-ary words of length m, 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 in A152139.

%D Leo J. Guibas and Andrew M. Odlyzko, String overlaps, pattern matching and nontransitive games, Journal of Combinatorial Theory Series A, 30 (1981), 183-208.

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

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

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

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

%K hard,more,nonn

%O 1,2

%A _Paul Leopardi_, Dec 15 2008, Dec 28 2008

%E a(11)=7897, a(12)=13221 added by _Paul Leopardi_, Apr 20 2010