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

Question

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$)

Answer 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$.

Answer 2

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}$$

Answer 3

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])



-- find admissible binary words
adwords :: [[Integer]]
adwords = filter (\ws-> p1 ws && p2 ws && p3 ws && p4 ws) binwords


-- group admissible words by length
adwords' :: [[[Integer]]]
adwords' = groupBy (\xs ys->length xs == length ys) adwords

---

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}$$