|
|
A152959
|
|
Number of correlation classes for pairs of different words in an alphabet of size 4.
|
|
0
|
|
|
1, 6, 20, 55, 141, 324, 657, 1329, 2515, 4592, 7897, 13221
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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.
|
|
REFERENCES
|
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.
|
|
LINKS
|
|
|
EXAMPLE
|
Rahmann and Rivals [Table 1] has a(2)=6.
|
|
CROSSREFS
|
|
|
KEYWORD
|
hard,more,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|