Consider a general bit string of length $n$; how many bit strings are there that contain a substring $T$?

For example, given a bit string of length 6, how many are there that contain $110$ as a substring, and how many that contain $101$?

  • $\begingroup$ Your Question doesn't provide information that helps Readers tailor their response to your background in mathematics. There are only $64$ bit strings of length six, so you could simply count which of them contain those particular substrings. For a more general problem I've used a "transition matrix" approach to count the exact number of strings of length $n$ that contain a particular substring. $\endgroup$ – hardmath Jun 13 '18 at 18:27
  • 3
    $\begingroup$ Hint: Count the number of bitstrings that do not contain the substring. Depending on your substring you can develop a recursive approach. $\endgroup$ – S. M. Roch Jun 13 '18 at 18:33
  • $\begingroup$ Well... since the substring is of length 3, I would have $2^{3}$ ("free" positions) strings that do not contain it? (Considering the first example above) $\endgroup$ – Johnny Bueti Jun 13 '18 at 18:37
  • $\begingroup$ Also, @hardmath, this is all the information our professor gave to us; the two examples below are actual exercises. $\endgroup$ – Johnny Bueti Jun 13 '18 at 18:40
  • 1
    $\begingroup$ If this is from an introductory discrete math course, I doubt your instructor is expecting you to have a fully general solution to this problem. More likely, they want you know how to be able to do ad-hoc case-by-case analyses. However, if you are looking for a fully general solution, and you are very comfortable with generating functions, this is provided by the 'Goulden-Jackson cluster method.' See my answer here. $\endgroup$ – Jair Taylor Jun 13 '18 at 19:08

Given the comments, I think you should check the article here : https://oeis.org/A005251 in OEIS.

The mentioned recurrence formula is : a(n) = a(n-1) + a(n-2) + a(n-4) and it may be obtained by taking into account four kind of sequences:

$A_n$ : good sequences of length n that finish in 00

$B_n$ : good sequences of length n that finish in 01

$C_n$ : good sequences of length n that finish in 10

$D_n$ : good sequences of length n that finish in 11

and see what happens if we add one digit.

their sum $E_{n+1}$ would be expressed :

$$E_{n+1} = A_{n+1} + B_{n+1}+C_{n+1}+D_{n+1} = (A_n+B_n+C_n+D_n) + A_{n-1} + B_{n-1} + D_{n-1} = ....... =E_n + E_{n-1} + E_{n-3}$$

where the first four E's are 4, 7, 12, 21 for n = 2, 3, 4, 5 and they have to be obtained by hand.


Again, given the work around strings in the last days, there is a simple method to obtain a GF for the strings avoiding 110.

Suppose that we generate strings in the language $L = (1+0+110)^*$. There are two ways of obtaining the bad 110 in the process of building strings.

$\alpha = \ $ the hard way, by adding 0's and 1' to some previous string

$\beta = \ $ the short way, by adding directly a 110 to some previous string

for example, a string that contains two occurrences of 110 (there are no overlappings)

$w = ....110...110...$ may be obtained in four ways, depending on what method was used to derive each 110.

We have a multiplicity of 4 for $w$.

If we use a $-$ sign in the expression $(x+y-xxy)$ , the coefficient of the algebraic sum that describes the multiplicity of w changes from $4$ to $0$, because $1-1-1+1=0$. The four cases are $\alpha\alpha,\alpha\beta, \beta\alpha,\beta\beta $ where $\alpha\alpha$ means that the two $110's$ of $w$ were obtained the hard way.

So happens for other strings with multiplicities of 8, 16, 32...

It remains to write the GF

$1+(x+y-xxy)+(x+y-xxy)^2+... = \frac{1}{1 -x - y + xxy}$

We have obtained https://oeis.org/A000071, the Fibonacci numbers - 1 in OEIS.


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.