# Counting the number of bit strings containing a substring

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

• 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. – hardmath Jun 13 '18 at 18:27
• Hint: Count the number of bitstrings that do not contain the substring. Depending on your substring you can develop a recursive approach. – S. M. Roch Jun 13 '18 at 18:33
• 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) – Johnny Bueti Jun 13 '18 at 18:37
• Also, @hardmath, this is all the information our professor gave to us; the two examples below are actual exercises. – Johnny Bueti Jun 13 '18 at 18:40
• 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. – 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.