2
$\begingroup$

There is something about counting bitstrings and the format of the solutions I didn't really understand yet.

Given a bitstring problem that asks to elementarily count how many bitstrings of length 36 there are that contain exactly 5 $\{1\}$ in the first 10 posititions and the $\{10100101\}$ substring in the last 20 positions, finding it out is pretty straightforward.

Since the first 10 positions need to contain exactly 5 $\{1\}$, you find out the number of all the possible combinations containing maximum five ones:

$${10 \choose 5}$$

We have no information about the next 16 positions, so that is $2^{16}$ more combinations, and thus far we have:

$${10 \choose 5} \cdot 2^{16}$$

many combinations.

Now the substring:

  • there are $\{10100101\} \cdot 2^{12}$ bitstrings with no overlapping; $20 - 8 + 1 = 13 \rightarrow {13 \choose 1} \cdot 2^{12}$

  • there are $\{1010010100101\} \cdot 2^{7}$ bitstrings with single overlapping, same goes as you overlap the starting $1$ and the one at the end, so ${8 \choose 1} \cdot 2^{7}, {6 \choose 1} \cdot 2^{5}$

  • there are $2\cdot \{10100101\} \cdot 2^{4}$ bitstrings as the substring repeats itself once, so ${6 \choose 2} \cdot 2^{4}$

  • there are $\{101001010010100101\} \cdot 2^{2}$ bitstrings with double overlapping, and considering also all the other possibilities you have ${3 \choose 1} \cdot 2^{2}, {1 \choose 1} \cdot 2^{0}, {1 \choose 1} \cdot 2^{0}$

Since $\{10100101\} \cdot 2^{12}$ "spans" all the other combinations below and are thus included within it, shouldn't we remove all the overlapping and repeating substrings from the universe $\{10100101\} \cdot 2^{12}$? Given the number of substrings above, how should I then build the solution?

$\endgroup$
  • $\begingroup$ The number of binary strings of length $10$ with exactly five $1's$ is just $\binom {10}5$...there shouldn't be a multiplier of $2^5$. $\endgroup$ – lulu Jun 15 '18 at 15:26
  • $\begingroup$ My bad, fixed, thank you. $\endgroup$ – Fehniix Jun 15 '18 at 15:29
3
$\begingroup$

In order to calculate the number of binary strings of length $20$ containing the substring $10100101$ pretty much of all the hard work is already done. We just have to use the inclusion-exclusion principle and put all the intermediate results together.

The number of wanted strings is \begin{align*} &\binom{13}{1}2^{12}-\left(\binom{8}{1}2^7+\binom{6}{1}2^5+\binom{6}{2}2^4\right) +\left(\binom{3}{1}2^2+\binom{1}{1}2^0+\binom{1}{1}2^0\right)\\ &\qquad=53\,248-(1024+192+240)+(12+1+1)\\ &\qquad\,\,\color{blue}{=51\,806} \end{align*} which counts the number of binary strings of length $20$

  • containing the substring $10100101$ at least once

  • minus the number of strings where the substring occurs at least twice, including overlaps.

  • Since we have subtraced strings where the substring occurs at least three times (here in form of overlaps only) too often we have to add them for compensation.

We can check the result by applying another approach called the Goulden-Jackson Cluster Method.

We consider the set words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1\}$$ and the set $B=\{010100101\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^n$ being the number of searched words of length $n$.

According to the paper (p.7) the generating function $f(s)$ is \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=|\mathcal{V}|=2$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[10100101]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[10100101])&=-s^8-s^5\text{weight}(\mathcal{C}[10100101])\\ &\qquad\quad-s^7\text{weight}(\mathcal{C}[10100101])\\ \end{align*}

and get \begin{align*} \text{weight}(\mathcal{C})=-\frac{s^8}{1+s^5+s^7} \end{align*}

It follows

\begin{align*} f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2s+\frac{s^8}{1+s^5+s^7}}\\ &=\frac{1+s^5+s^7}{1-2s+s^5-2s^6+s^7-s^8}\\ \end{align*}

The coefficient $[s^n]$ in $f(s)$ gives the number of binary words of length $n$ which does not contain $10100101$. Since we want to count the number of words of length $20$ which do contain the word we take the generating function \begin{align*} \frac{1}{1-2s}=1+2s+4s^2+8s^3+\cdots \end{align*} which counts all binary words and subtract $f(s)$ from it.

We obtain with some help of Wolfram Alpha \begin{align*} \frac{1}{1-2s}-\frac{1+s^5+s^7}{1-2s+s^5-2s^6+s^7-s^8}&=s^8+4s^9+12s^{10}+32s^{11}+\cdots\\ &\qquad+\color{blue}{51\,806s^{20}}+\cdots \end{align*} in accordance with the calculation above.

$\endgroup$
  • $\begingroup$ Ah! So you have to add back the substrings that occur at least three times because they were already counted (and excluded) from the case in which it occurs at least two times and thus three times or more as well? Thank you! $\endgroup$ – Fehniix Jun 16 '18 at 11:45
  • $\begingroup$ @Fehniix: Correct. You're welcome. :-) $\endgroup$ – Markus Scheuer Jun 16 '18 at 11:50
  • $\begingroup$ And also, were it the case in which there was a substring repeating itself four times, I would have to subtract the strings that repeat themselves at least two times, add back those that repeat at least three times, and since those that repeat themselves four times are already included in those that repeat at least three times, I would have to exclude them, correct? $\endgroup$ – Fehniix Jun 16 '18 at 11:50

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.