3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Joffan Jul 21 '16 at 15:58
  • $\begingroup$ Yes - you are right Joffan, I will edit the answer I posted. $\endgroup$ – Michael Mc Gettrick Jul 21 '16 at 16:16
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.