|
| |
|
|
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; 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, 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.
|
|
|
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.
|
|
|
EXAMPLE
| Rahmann and Rivals [Table 1] has a(2)=6.
|
|
|
CROSSREFS
| Cf. A152139. See also A005434, which treats autocorrelations.
Sequence in context: A027993 A028492 A059822 * A109903 A201149 A014480
Adjacent sequences: A152956 A152957 A152958 * A152960 A152961 A152962
|
|
|
KEYWORD
| hard,nonn
|
|
|
AUTHOR
| Paul C. Leopardi (paul.leopardi(AT)anu.edu.au), Dec 15 2008, Dec 28 2008
|
|
|
EXTENSIONS
| Added a(11)=7897, a(12)=13221. Paul C. Leopardi (paul.leopardi(AT)anu.edu.au), Apr 20 2010
|
| |
|
|
