0
$\begingroup$

Given a binary string {${x_{1},x_{2},x_{3},...,x_{n}}$} find all "legal" strings with more than $2$ consecutive ($ 1's)$.

For example for $N=7$ , we have $16$

With $3 (1's)$: {$1,1,1,0,0,0,0$} , {$0,1,1,1,0,0,0$} , {$0,0,1,1,1,0,0$} , {$0,0,0,1,1,1,0$} , {$0,0,0,0,1,1,1$}

With $4 (1's)$: {$1,1,1,1,0,0,0$} , {$0,1,1,1,1,0,0$} , {$0,0,1,1,1,1,0$} ,{$0,0,0,1,1,1,1$}

With $5 (1's)$: {$1,1,1,1,1,0,0$} , {$0,1,1,1,1,1,0$} ,{$0,0,1,1,1,1,1$}

With $6 (1's)$: {$1,1,1,1,1,1,0$} , {$0,1,1,1,1,1,1$} , {$1,1,1,0,1,1,1$}

With $7 (1's)$: {$1,1,1,1,1,1,1$}

Is there elegant way to calculate the number of such "legal "sub strings for any $N$.

$ Edit: $ A "legal" string is a string in which all consecutive $(1's)$ are with length $\geq 3$

$\endgroup$
  • $\begingroup$ You seem to be omitting cases. For instance, the string $(1, 1, 1, 0, 1, 0, 1)$ has three consecutive ones. $\endgroup$ – N. F. Taussig May 30 '18 at 22:13
  • $\begingroup$ Sorry my bad , I meant if there are consecutive 1's all should be consecutive with length at least 3 . $\endgroup$ – Noodle May 30 '18 at 22:21
  • $\begingroup$ {${1,1,1,0,1,1,1}$} is alright because it can be divided like {1,1,1} , {0} , {1,1,1} $\endgroup$ – Noodle May 30 '18 at 22:36
  • 1
    $\begingroup$ I think it'll help if you include $0$($1$'s) in the count: $\{0,0,0,0,0,0,0\}$. $\endgroup$ – Barry Cipra May 30 '18 at 22:44
  • 1
    $\begingroup$ The title talks of substrings but the question does not. We are finding the number of strings. $\endgroup$ – Ross Millikan May 30 '18 at 23:56
2
$\begingroup$

Let $B_n$ count the number of $n$-bit strings in which any $1$'s come in Bunches of $3$ or more. This is the count we want. Let $A_n$ count the number of $n$-bit strings which can start with an Arbitrary number of $1$'s, but as soon as a $0$ appears, any subsequent $1$'s occur in bunches of $3$ or more. It's easy to see that $B_1=B_2=1$ and $B_3=2$, while $A_1=2$, $A_2=3$, and $A_3=4$. What's important is the entangled recursion for $n\ge4$:

$$\begin{align} A_n&=A_{n-1}+B_{n-1}\\ B_n&=B_{n-1}+A_{n-3} \end{align}$$

That is, if the first digit of an $A$-type string is a $1$, the remaining $n-1$ digits are of $A$-type, while if the first digit is a $0$, the rest must be of $B$-type; likewise, if the first digit of a $B$-type string is a $0$, the remaining $n-1$ digits must be of $B$-type, while if the first digit is a $1$, then the next two must also be $1$'s, but the remaining $n-3$ digits can start with an arbitrary number of $1$'s, i.e., they are of $A$-type.

We can now compute

$$\begin{align} A_4&=4+2=6\\ B_4&=2+2=4\\ \\ A_5&=6+4=10\\ B_5&=4+3=7\\ \\ A_6&=10+7=17\\ B_6&=7+4=11\\ \\ A_7&=17+11=28\\ B_7&=11+6=17 \end{align}$$

Note, $B_7=17$ agrees with what the OP found for $N=7$, provided you include the all-$0$ string $\{0,0,0,0,0,0,0\}$ in the count.

$\endgroup$
  • $\begingroup$ The recursion is nice and correct (+1), and check with sum provided in my answer. It would be interesting to further develop the correspondence. $\endgroup$ – G Cab May 31 '18 at 20:25
1
$\begingroup$

Consider a binary string with $s$ "$1$"'s and $m=n-s$ "$0$"'s in total. Let's put an additional (dummy) fixed $0$ at the start and at the end of the string. We individuate as a run the consecutive $1$'s between two zeros, thereby including runs of null length.

Bernoulli_Run_1

With this scheme we have a fixed number of $m+1$ runs. If we sequentially enumerate the length of each run so individuated, we construct a bijection with the number of weak compositions of $s$ into $m+1$ parts.

In your case we want that each part be either $0$ or greater than $2$, i.e. $$ \eqalign{ & N_s (s,m) = \cr & = {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm integer}\;x_{\,j} \in \left\{ 0 \right\} \cup \left\{ {3,4, \cdots ,\left( s \right)} \right\} \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,m + 1} = s \hfill \cr} \right.\quad = \cr & = \sum\limits_{0\, \le \,k\, \le \,m + 1} {\left( \matrix{ m + 1 \cr k \cr} \right){\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm integer}\;x_{\,j} \left\{ {3,4, \cdots ,\left( s \right)} \right\} \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,k} = s \hfill \cr} \right.} \quad = \cr & = \sum\limits_{0\, \le \,k\, \le \,m + 1} {\left( \matrix{ m + 1 \cr k \cr} \right){\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm integer}\;y_{\,j} \left\{ {1,2, \cdots ,\left( {s - k} \right)} \right\} \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,k} = s - 2k \hfill \cr} \right.} \quad \cr} $$

The set in $y$ corresponds to the (standard) compositions of $s-2k$ into $k$ parts, thus $$ \eqalign{ & N_s (s,m) = \sum\limits_{0\, \le \,k\, \le \,\min \left( {m + 1,\,s/3} \right)} { \binom{m+1}{k} \binom{s-1-2k}{k-1} } = \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,\min \left( {m + 1,\,s/3} \right)} \right)} { \binom{m+1}{m+1-k} \binom{s-1-2k}{s-3k} } \cr} $$

And the number you ask (also considering the null string) follows easily to be $$ \eqalign{ & N(n) = \sum\limits_{0\, \le \,s\, \le \,n} {\;\sum\limits_{0\, \le \,k\,\left( { \le \,\min \left( {m + 1,\,s/3} \right)} \right)} { \binom{m+1}{m+1-k} \binom{s-1-2k}{s-3k} } } = \quad \quad (1) \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,n/3} \right)} {\;\sum\limits_{0\, \le \,s\, \le \,n} { \binom{n+1-s}{n+1-k-s} \binom{s-1-2k}{s-3k} }} = \quad \quad (2) \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,n/3} \right)} {\;\left( {\left( {\sum\limits_{0\, \le \,s\, \le \,n + 1} { \binom{n+1-s}{n+1-k-s} \binom{s-1-2k}{s-3k} } } \right) - \left( \matrix{0 \cr 0 - k \cr} \right)\left( \matrix{ n - 2k \cr n + 1 - 3k \cr} \right) } \right)} = \quad \quad (3) \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,n/3} \right)} {\sum\limits_{\left( {0\, \le } \right)\,s\,\left( { \le \,n + 1} \right)} { \binom{n+1-s}{n+1-k-s} \binom{s-1-2k}{s-3k} } } = \quad \quad (4) \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,(n + 1)/4} \right)} { \binom{n+1-2k}{n+1-4k} } \quad \quad (5) \cr} $$ where:
(2) : exchange summation order and replace $m$ with $n-s$;
(3) : extend the summation in $s$ to the whole range and deducting the term $s=n+1$;
(4) : the subtracted term is null everywhere;
(5) : "double convolution".

So finally
the number of binary strings where the ones - if present - appears only in runs of three or more consecutive
is given by the closed sum $$ N(n) = \sum\limits_{0\, \le \,k\,\left( { \le \,(n + 1)/4} \right)} { \binom{n+1-2k}{n+1-4k} } $$

Note that for $n=0,\cdots, 10$ we get for $N$ $$1, 1, 1, 2, 4, 7, 11, 17, 27, 44, 72$$ which checks with the answer by Barry Cipra, with $$ B_{\,n} = N(n)\quad A_{\,n} = \sum\limits_{0\, \le \,k\,} { \binom{n+1-2k}{n-4k} } $$

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