2
$\begingroup$

Let's say $A_n$ is the number of binary string that has length $n$ and does not contain the substring 101. Calculate $A_n$ for $n=1,2\cdots8.$ Find a recurrence relation for $A_n$. What does the solution of that recurrence look like?

These are the solutions that I have found for calculations for $A_n$. $1, 4, 7, 12, 20, 32, 48, 96$.

I've calculated this by hand. But how I do find the recurrence? I see that 4, 7, 12, 30 are Fibonacci - 1, but not after or before that.

But I'm not sure how to do this or if this is even correct.

$\endgroup$
6
  • $\begingroup$ I think your values may be counting the complement; those strings that DO contain $101$, no? $\endgroup$
    – lulu
    Dec 9, 2018 at 12:09
  • $\begingroup$ Many similar questions have been asked on the site...this question for instance. $\endgroup$
    – lulu
    Dec 9, 2018 at 12:10
  • $\begingroup$ You should double check your values of $A_n$, they are all wrong. A hint: if you are having trouble getting a recurrence, let $B_n$ be strings avoiding 101 which end in 0, an let $C_n$ be strong avoiding 101 ending in 1, then get a mutual recurrence for those. $\endgroup$ Dec 9, 2018 at 17:12
  • $\begingroup$ Thank you. I've edited my question to add the correct solution, but I'm still not sure how to find and solve the recurrence? $\endgroup$
    – ponikoli
    Dec 10, 2018 at 19:15
  • $\begingroup$ Try to proceed similarly to this answer. $\endgroup$ Dec 11, 2018 at 5:30

1 Answer 1

6
$\begingroup$

We count the number $a(n)$ of valid binary strings, i.e. strings which do not contain $101$ by partitioning them according to their matching length with the initial parts of the bad string $101$.

\begin{align*} a_n=a^{[\emptyset]}_n+a^{[1]}_n+a^{[01]}_n\tag{1} \end{align*}

  • The number $a^{[\emptyset]}_n$ counts the valid strings of length $n$ which do not start with the rightmost character of the bad word $10\color{blue}{1}$, i.e. start with $0$.

  • The number $a^{[1]}_n$ counts the valid strings of length $n$ which do start with the rightmost character of the bad word $10\color{blue}{1}$, i.e. $\color{blue}{1}$.

  • The number $a^{[01]}_n$ counts the valid strings of length $n$ which do start with the two rightmost characters of the bad word $1\color{blue}{01}$, i.e. start with $\color{blue}{01}$.

We get a relationship between valid strings of length $n$ with those of length $n+1$ as follows:

  • If a word counted by $a^{[\emptyset]}_n$ is appended by $0$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. If it is appended by $1$ from the left it contributes to $a^{[1]}_{n+1}$.

  • If a word counted by $a^{[1]}_n$ is appended by $0$ from the left it contributes to $a^{[01]}_{n+1}$. If it is appended by $1$ from the left it contributes to $a^{[1]}_{n+1}$.

  • If a word counted by $a^{[01]}_n$ is appended by $0$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. Appending from the left by $1$ is not allowed since then we have an invalid string starting with $101$.

This relationship can be written as \begin{align*} a^{[\emptyset]}_{n+1}&=a^{[\emptyset]}_{n}+a^{[01]}_{n}\tag{2}\\ a^{[1]}_{n+1}&=a^{[\emptyset]}_{n}+a^{[1]}_n\tag{3}\\ a^{[01]}_{n+1}&=a^{[1]}_n\tag{4} \end{align*}

We can now derive a recurrence relation from (1) - (4):

We obtain for $n\geq 3$: \begin{align*} \color{blue}{a_{n+1}}&=a^{[\emptyset]}_{n+1}+a^{[1]}_{n+1}+a^{[01]}_{n+1}\tag{$ \to (1)$}\\ &=\left(a^{[\emptyset]}_{n}+a^{[01]}_{n}\right)+\left(a^{[\emptyset]}_{n}+a^{[1]}_n\right)+\left(a^{[1]}_n\right)\tag{$\to (2),(3),(4)$}\\ &=2a_n-a^{[01]}_{n}\tag{$\to (1)$}\\ &=2a_n-a^{[1]}_{n-1}\tag{$\to (4)$}\\ &=2a_n-a_{n-2}+a^{[\emptyset]}_{n-2}+a^{[01]}_{n-2}\tag{$\to (1)$}\\ &=2a_n-a_{n-2}+a^{[\emptyset]}_{n-3}+a^{[01]}_{n-3}+a^{[1]}_{n-3}\tag{$\to (2),(4)$}\\ &\,\,\color{blue}{=2a_n-a_{n-2}+a_{n-3}}\tag{$\to (1)$} \end{align*}

We finally derive manually the starting values

\begin{align*} \color{blue}{a_0=1,a_1=2,a_2=4,a_3=7} \end{align*}

and obtain a sequence $(a_n)_{n\geq 0}$ starting with \begin{align*} (a_n)_{n\geq 0}=(1,2,4,7,12,21,37,65,114,200,351,\ldots) \end{align*}

Hint: We have $a_5=\color{blue}{21}$ valid strings of length $5$. The $2^5-21=11$ invalid strings are \begin{align*} \color{blue}{101}00\qquad0\color{blue}{101}0\qquad00\color{blue}{101}\\ \color{blue}{101}01\qquad0\color{blue}{101}1\qquad01\color{blue}{101}\\ \color{blue}{101}10\qquad1\color{blue}{101}0\qquad\color{lightgrey}{10101}\\ \color{blue}{101}11\qquad1\color{blue}{101}1\qquad11\color{blue}{101} \end{align*}

$\endgroup$
9
  • $\begingroup$ +1 Your answers (not just this one) are so good and clear, there needs to be a SUBSCRIBE button. :) $\endgroup$
    – antkam
    Mar 26, 2019 at 14:06
  • $\begingroup$ @antkam: Many thanks for your nice comment. It's good to see the answer is useful. :-) $\endgroup$ Mar 26, 2019 at 15:09
  • $\begingroup$ @MarkusScheuer This is very beautiful answer +1. I want to ask something. I asked a similar question today such that math.stackexchange.com/questions/4096861/…. When i want to solve this question with my way in part $a-)$ , it seems that my solution is wrong because i found that it must be $a_n=2a_{n-1}-a_{n-3}$ but it break down for $n>4$. If you have free time ,can you look at my question in the link and say that why my solution is wrong ? I really wonder it because it works in my question but does not this $\endgroup$ Apr 10, 2021 at 20:04
  • 1
    $\begingroup$ @Will: You might find this answer helpful. Kind regards, $\endgroup$ Jun 26, 2023 at 19:51
  • 1
    $\begingroup$ thanks Mr Markus @epi163sqrt i appreciate your help a lot $\endgroup$
    – Will
    Jun 27, 2023 at 0:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .