Home > Numbers > Sequences
| Bits adjacent to 1 (Posted on 2022-11-15) |
 |
A string of N binary bits has the property that every bit is adjacent to a '1' bit. An example for N=12 is 111011011110.
Note that 010 is not a valid sequence, the 1 bit is not adjacent to any other 1 bit.
How many valid binary sequences of length 20 exist?
What is the smallest length N such that there are over a hundred thousand valid binary sequences?
|
|
Submitted by Brian Smith
|
|
Rating: 5.0000 (1 votes)
|
|
|
Solution:
|
(Hide)
|
Let S(n) be the number of n bit long strings that have the desired property. By direct construction
S(2)=1 from {11}, S(3)=3 from {011, 110, 111}, S(4)=4 from {0110, 0111, 1110, 1111}, S(5)=5 from {01110, 01111, 11011, 11110, 11111}, S(6)=9 from {011011, 011110, 011111, 110011, 110110, 110111, 111011, 111110, 111111}.
There is a one-to-one relation between strings of length n-1 ending in 1 and strings of length n ending in 0. Example: {01111, 11011, 11111} are the three length 5 strings ending in 1, which correspond to {011110, 110110, 111110} which are the three length 6 strings ending in 0. So if L(n) is the number of strings ending in 1 then S(n) = L(n) + L(n-1).
The first few terms of L(n) are L(2)=1 from {11}, L(3)=2 from {011, 111}, L(4)=2 from {0111, 1111}, L(5)=3 from {01111, 11011, 11111}, L(6)=6 from {011011, 011111, 110011, 110111, 111011, 111111}.
L(n) can be built recursively, first by appending a '1' to a string of length n-1, appending '011' to a string of length n-3, or appending '0011' to a string of length n-4.
So then L(n) = L(n-1) + L(n-3) + L(n-4). Then substitute into S(n) = L(n) + L(n-1):
S(n) = L(n) + L(n-1)
S(n) = (L(n-1) + L(n-3) + L(n-4)) + (L(n-2) + L(n-4) + L(n-5))
S(n) = (L(n-1) + L(n-2)) + (L(n-3) + L(n-4)) + (L(n-4) + L(n-5))
S(n) = S(n-1) + S(n-3) + S(n-4).
The recursive formula along with initial terms (starting at n=2) 1, 3, 4, 5, 9 makes it very easy to extend the sequence:
1, 3, 4, 5, 9, 16, 25, 39, 64, 105, 169, 272, 441, 715, 1156, 1869, 3025, 4896, 7921, 12815, 20736, 33553, 54289, 87840, 142129, ....
S(20) = 7921 and the first term exceeding a hundred thousand occurs at length 26 with S(26)=142129.
A search of the OEIS identifies this as Sequence A195971 |
Comments: (
You must be logged in to post comments.)
|
|
Please log in:
Forums (0)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
