# Number of binary strings of length $n$ satisfying specific (ad-hoc) conditions

Count the number of binary strings of length $n$ that satisfy the following additional conditions:

a) Two zeroes in a row are not allowed

b) Three ones in a row are not allowed

c) The string cannot begin or end with $11$ (and of course because of a) above neither can it begin or end with $00$)

As a regular expression, the string matches ^1?(011?)*01?$ for$n>1$The minimum number of zeroes is$\lfloor \frac{n+2}{3}\rfloor$. The maximum number of zeroes is$\lfloor \frac{n+1}{2}\rfloor$. For each count of zeroes, you can set up a base string consisting of alternating zeroes and ones,$0101\ldots10$, with$k$zeroes, length$2k-1$, then insert$n-2k+1$ones into the string in a choice of$k+1$locations,${k+1 \choose n-2k+1}$. Thus the answer is: $$\sum_{k=\lfloor \frac{n+2}{3}\rfloor}^{\lfloor \frac{n+1}{2}\rfloor}{k+1 \choose n-2k+1}$$ mmm - I probably posted the question too quickly, anyway in last few hours, here is I think the solution in terms of recurrence relations: Let$N(n)$be the number of binary strings satisfying the conditions. Let$N_1(n)$be the number of binary strings ending in a$1$satisfying the conditions. Let$N_0(n)$be the number of binary strings ending in a$0$satisfying the conditions. Then $$N_0(n) = N_1(n-1) + N_0(n-3)$$ $$N_1(n) = N_0(n-1)$$ $$N(n) = N(n-2) + N(n-3)$$ with$N_0(1) = N_1(1) = N_0(2) = N_1(2) = N_0(3) = N_1(3)=1$. • Not sure how you get$N_0(3) = 2$. I can only see$010$as an option there. Likewise$N_1(3)$, what else is possible except$101$? – Joffan Jul 21 '16 at 15:58 • Yes - you are right Joffan, I will edit the answer I posted. – Michael Mc Gettrick Jul 21 '16 at 16:16 Let$\mathcal W_n$be the set of words of length$n$over$\{0,1\}$. Let$\mathcal A_n \subset \mathcal W_n$be the set of admissible words. If$n = 2$, $$\mathcal W_2 = \{00,01,10,11\}$$ $$\mathcal A_2 = \{01,10\}$$ If$n = 3$, $$\mathcal W_3 = \{000,001,010,011,100,101,110,111\}$$ $$\mathcal A_3 = \{010,101\}$$ If$n = 4$, $$\mathcal W_4 = \{0000,0001,0010,0011,0100,0101,0110,0111,\\ \qquad \quad 1000,1001,1010,1011,1100,1101,1110,1111\}$$ $$\mathcal A_4 = \{0101,0110,1010\}$$ Note that$011$is non-admissible, whereas$0110$is admissible. The following Haskell script generates all binary words and filters the admissible ones: import Data.List -- generate all binary words binwords :: [[Integer]] binwords = concat$ iterate (concat . map (\xs -> [ xs ++ [s] | s <- [0,1] ])) [[]]

-- define predicates
p1, p2, p3, p4 :: [Integer] -> Bool
p1 = not . (isInfixOf  [0,0])
p2 = not . (isInfixOf  [1,1,1])
p3 = not . (isPrefixOf [1,1])
p4 = not . (isSuffixOf [1,1])

adwords = filter (\ws-> p1 ws && p2 ws && p3 ws && p4 ws) binwords

-- group admissible words by length


Admissible words of length $2$

λ> adwords' !! 2
[[0,1],[1,0]]


Admissible words of length $3$

λ> adwords' !! 3
[[0,1,0],[1,0,1]]


Admissible words of length $4$

λ> adwords' !! 4
[[0,1,0,1],[0,1,1,0],[1,0,1,0]]


Admissible words of length $5$

λ> adwords' !! 5
[[0,1,0,1,0],[0,1,1,0,1],[1,0,1,0,1],[1,0,1,1,0]]


How many admissible words are there of each length?

λ> take 20 $map length adwords' [1,2,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200]  Searching for 2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151,200 in the Online Encyclopedia of Integer Sequences (OEIS), we find sequence A000931, the Padovan sequence, which is given by $$a(n) = a(n-2) + a(n-3)$$ with initial conditions$a(0)=1$and$a(1)=a(2)=0$. Let$f (n)$be the number of admissible binary words of length$n$. Hence,$f : \mathbb N \to \mathbb N\$ seems to be defined by

$$f (n) = \begin{cases} 1 & \text{if } n = 0\\ 2 & \text{if } n \in \{1,2,3\}\\ 3 & \text{if } n = 4\\ f(n-2) + f(n-3) & \text{if } n \ge 5\end{cases}$$