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