|
Search: id:A045690
|
|
|
| A045690 |
|
Number of binary words of length n (beginning with 0) whose autocorrelation function is the indicator of a singleton. |
|
+0
6
|
|
| 1, 1, 2, 3, 6, 10, 20, 37, 74, 142, 284, 558, 1116, 2212, 4424, 8811, 17622, 35170, 70340, 140538, 281076, 561868, 1123736, 2246914, 4493828, 8986540, 17973080, 35943948, 71887896, 143771368, 287542736, 575076661, 1150153322, 2300289022
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
The number of binary strings sharing the same autocorrelations.
|
|
REFERENCES
|
E. Rivals, S. Rahmann, Combinatorics of Periods in Strings, Journal of Combinatorial Theory - Series A, Vol. 104(1) (2003), pp. 95-113.
|
|
LINKS
|
T. Sillke, How many words have the same autocorrelation value?
E. H. Rivals, Autocorrelation of Strings.
E. H. Rivals, S. Rahmann Combinatorics of Periods in Strings
|
|
FORMULA
|
a[ 2n ] = 2 a[ 2n-1 ] - a[ n ] for n >= 1; a[ 2n+1 ] = 2 a[ 2n ] for n >= 1
a(2n)=2a(2n-1)-a(n) for n >= 1; a(2n+1)=2a(2n) for n >= 1.
|
|
PROGRAM
|
(PARI) a(n)=if(n<2, n>0, 2*a(n-1)-(1-n%2)*a(n\2))
|
|
CROSSREFS
|
Cf. A002083, A005434. A003000 = 2*a(n) for n > 0.
Sequence in context: A007562 A008929 A066062 this_sequence A007148 A093371 A003214
Adjacent sequences: A045687 A045688 A045689 this_sequence A045691 A045692 A045693
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
Torsten.Sillke(AT)uni-bielefeld.de
|
|
EXTENSIONS
|
More terms from James A. Sellers (sellersj(AT)math.psu.edu). Additional comments from Michael Somos, Jun 09 2000.
|
|
|
Search completed in 0.003 seconds
|
