How many numbers are in this set?

Question

Let M a positive integer is called “Minos” if in its binary representation, any two consecutive appearance of digit 1 are separated by 2 or more 0. Example 36= 100100 (binary) is “Minos” number, but 37=100101 not.

How many nonnegative integers that can be represented as binary sequence of length 20 (leading zeros allowed) are ‘Minos’?

My tough:

C=# of ceros N=# of ones T=# total

*) Two ceros always must be together, when are all 0 . In this case the number 0 is Minos.

*) Now 1 one and 19 ceros 20 different numbers.

*) Now 2 ones and 18 ceros then 20Cn2 In conclusion I’m thinking the solution will be all the sum of all the combination of numbers taken in group of 2.

Note: Regarding my answer, I posted because something doesn’t sound quite right, and I cannot see how can I proceed to calculate the correct answer, and how lead into it. Thanks.

Answer 1

Let $a_n$ be the number of Minos numbers of length $n$. It is not hard to compute $a_1$, $a_2$, and $a_3$.

A Minos number of length $n$ can end in a) $0$ or b) $1$. If $n\ge 2$, the number of Minos numbers that end in $0$ is $a_{n-1}$.

For ending in $1$, where $n\ge 4$, the number obtained by stripping off the $1$ must end in $00$, and the number obtained by stripping off the $00$ must be a Minos number of length $n-3$, and all Minos numbers of length $n$ that end in $1$ can be obtained by appending $001$ to a Minos number of length $n-3$. So there are $a_{n-3}$ Minos numbers of length $n$ that end in $1$.

For $n\ge 4$ we have obtained the recurrence $$a_n=a_{n-1}+a_{n-3}.$$
We can now, a little painfully, use the recurrence to find $a_{20}$.

Answer 2

Try to set up a recurrence on the length $n$, denote the number of Minos of length $n$ by $M_n$. It is $M_0 = 1$, $M_1 = 2$ ($\{0, 1\}$), $M_2 = 3$ ($\{00, 01, 10\}$)

OK, now consider a Minos of length $n$. If the last digit is $0$, before that came a Minos of length $n - 1$. If the last digit is $1$, it must really end in $001$, before that you have a Minos of length $n - 3$. So:

$$M_{n + 3} = M_n + M_{n + 2}$$

Just churn through the numbers starting with $n = 0$.

Answer 3

Let $m$ be the number of 1's in a Minos number of length 20, so $0\le m\le7$.

If we insert two zeros between each consecutive pairs of 1's,

we have $(20-m)-(2m-2)=22-3m$ zeros left to distribute in the gaps created by the $m$ 1's;

and there are $\dbinom{22-2m}{m}$ ways to do this $\;\;$(for $m\ge2$).

Therefore there are $\displaystyle\sum_{m=0}^7\binom{22-2m}{m}=2745$ Minos numbers of length 20.