|
Search: id:A118645
|
|
|
| A118645 |
|
Number of binary strings of length n+2 such that there exist 3 consecutive digits such that 2 of them are ones. |
|
+0
1
|
|
| 4, 10, 23, 51, 109, 228, 471, 964, 1960, 3967, 8003, 16107, 32362, 64941, 130200, 260866, 522415, 1045831, 2093129, 4188408, 8379967, 16764552, 33535872, 67081663, 134177863, 268377031, 536785286, 1073616333, 2147299732
(list; graph; listen)
|
|
|
OFFSET
|
0,1
|
|
|
COMMENT
|
For n>=3, a(n) = 2^n - the sum of all terms in the n-3th power of the 4 X 4 matrix [[1 1 0 0] [0 0 1 0] [0 0 0 1] [1 1 0 0]] because this matrix represents the transitions from the state where the last three bits are 000, 001, 010, 100 to the state after the next bit, always avoiding two 1's out of the last three bits. - Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), Aug 04 2006
Complementary to A048625 which starts 4,6,9,13,19,28,41,60,88,129,189. They sum to 2^(n+2). A048625 is a subsequence of A000930, A068921 and A078012. All of them are generated by recursive equation a(n) = a(n-1) + a(n-3). - Tanya Khovanova (tanyakh(AT)yahoo.com), Aug 22 2006
|
|
FORMULA
|
a(n) = 3*2^(n-1) + a(n-1) + a(n-3) - Tanya Khovanova (tanyakh(AT)yahoo.com), Aug 22 2006
|
|
CROSSREFS
|
Sequence in context: A084446 A001980 A057750 this_sequence A137531 A102549 A008258
Adjacent sequences: A118642 A118643 A118644 this_sequence A118646 A118647 A118648
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Tanya Khovanova (tanyakh(AT)yahoo.com), May 10 2006
|
|
EXTENSIONS
|
More terms from Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), Aug 04 2006
|
|
|
Search completed in 0.002 seconds
|
