Find a recurrence relation for the number of bit strings of length $n$ by Goulden-Jackson

Question

I am working over Goulden -Jackson Method, I tried to undergo every possible question type.

I obtained the following questions from Rosen's Discrete Mathematics and Its Applications. I solved them by classical way, but when I tried to solve them via Goulden - Jackson, I got stuck.

a-) Find a recurrence relation for the number of bit strings of length $n$ which do not contain three consecutive zeros

My work = The bad word is $000$ , but it has two overlapping such that $0,00$ . Unfortunately, I do not know how to approach when there are two different overlapping words. I got stuck there.

b-) How many bit strings of length $n$ contain either five consecutive zeros or five consecutive ones.

My work = I thought that I can reach the solution by all cases - $(00000,11111)$ are bad words. In this situation, I reached $\frac{1}{1-2x} - \frac{1}{1-2x+2x^5}$ , but when I convert it into recurrence form, it does not satisfy the desired result.

c-) How many bit strings of length $n$ contain either three consecutive zeros or four consecutive ones.

My Work = It has the same logic as part $b$

I hope to find answers for my questions. Thanks for your works.

Answer 1

Here we consider the cases (b) and (c). We apply the Goulden-Jackson Cluster Method following the presentation by J. Noonan and D. Zeilberger. We start with

Case (b):

We consider the set of words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1\}$$ and the set $B=\{00000,11111\}$ of bad words. We derive a generating function $A(x)$ with the coefficient of $x^n$ being the number of words of length $n$ avoiding bad words.

Since we are looking for the number of words of length $n$ which contain either $00000$ or $11111$ a generating function $B(x)$ for the number of wanted words is \begin{align*} B(x) = \frac{1}{1-2x}-A(x)\tag{1.1} \end{align*}

According to the paper (p.7) the generating function $A(x)$ is \begin{align*} A(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\tag{1.2} \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}[00000])+\text{weight}(\mathcal{C}[11111])\tag{1.3} \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[00000])&=-x^5-(x+x^2+x^3+x^4)\text{weight}(\mathcal{C}[00000])\\ \end{align*} and get \begin{align*} \text{weight}(\mathcal{C}[00000])&=-\frac{x^5}{1+x+x^2+x^3+x^4}\\ &=-\frac{x^5(1-x)}{1-x^5}\\ \text{weight}(\mathcal{C}[11111])&=-\frac{x^5(1-x)}{1-x^5} \end{align*} From (1.3) we obtain \begin{align*} \text{weight}(\mathcal{C})&=\text{weight}(\mathcal{C}[00000])+\text{weight}(\mathcal{C}[11111])\\ &=-\frac{2x^5(1-x)}{1-x^5} \end{align*} It follows from (1.1) and (1.2) \begin{align*} B(x)&=\frac{1}{1-2x}-\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2x}-\frac{1}{1-2x+\frac{2x^5(1-x)}{1-x^5}}\\ &=\frac{1}{1-2x}-\frac{1-x^5}{1-2x+x^5}\\ &=2x^5+6x^6+16x^7+\color{blue}{40}x^8+96x^9+\cdots\\ \end{align*}

The last line was calculated with the help of Wolfram Alpha. The coefficient of $x^{8}$ shows there are $40$ words of length $8$ which do contain either $00000$ or $11111$.

The $\color{blue}{40}$ valid words of length $8$ are: \begin{align*} \begin{array}{ccccc} 00000000&00000001&00000010&00000011&00000100\\ 00000101&00000110&00000111&00011111&00100000\\ 00111110&00111111&01000000&01000001&01011111\\ 01100000&01111100&01111101&01111110&01111111\\ 10000000&10000001&10000010&10000011&10011111\\ 10100000&10111110&10111111&11000000&11000001\\ 11011111&11100000&11111000&11111001&11111010\\ 11111011&11111100&11111101&11111110&11111111 \end{array} \end{align*}

Case (c):

We consider the set of words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1\}$$ and the set $B=\{000,1111\}$ of bad words. We derive a generating function $C(x)$ with the coefficient of $x^n$ being the number of words of length $n$ avoiding bad words.

Since we are looking for the number of words of length $n$ which contain either $000$ or $1111$ a generating function $D(x)$ for the number of wanted words is \begin{align*} D(x) = \frac{1}{1-2x}-C(x)\tag{2.1} \end{align*}

According to the paper (p.7) the generating function $C(x)$ is \begin{align*} C(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\tag{2.2} \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}[000])+\text{weight}(\mathcal{C}[1111])\tag{2.3} \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[000])&=-x^3-(x+x^2)\text{weight}(\mathcal{C}[000])\\ \text{weight}(\mathcal{C}[1111])&=-x^3-(x+x^2+x^3)\text{weight}(\mathcal{C}[1111])\\ \end{align*} and get \begin{align*} \text{weight}(\mathcal{C}[000])&=-\frac{x^3}{1+x+x^2}\\ &=-\frac{x^3(1-x)}{1-x^3}\\ \text{weight}(\mathcal{C}[1111])&=-\frac{x^3}{1+x+x^2+x^3}\\ &=-\frac{x^4(1-x)}{1-x^4} \end{align*} From (2.3) we obtain \begin{align*} \text{weight}(\mathcal{C})&=\text{weight}(\mathcal{C}[000])+\text{weight}(\mathcal{C}[1111])\\ &=-\frac{x^3(1-x)}{1-x^3}-\frac{x^4(1-x)}{1-x^4} \end{align*} It follows from (2.1) and (2.2) \begin{align*} C(x)&=\frac{1}{1-2x}-\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2x}-\frac{1}{1-2x+\frac{x^3(1-x)}{1-x^3}+\frac{x^4(1-x)}{1-x^4}}\\ &=\frac{1}{1-2x}-\frac{1+2x+3x^3+3x^3+2x^4+x^5}{1-x^2-2x^3-2x^4-x^5}\\ &=x^3+4x^4+11x^5+28x^6+\color{blue}{65}x^7+147x^8+\cdots\\ \end{align*}

The last line was calculated with the help of Wolfram Alpha. The coefficient of $x^{7}$ shows there are $65$ words of length $7$ which do contain either $000$ or $1111$.

The $\color{blue}{65}$ valid words of length $7$ are: \begin{align*} \begin{array}{ccccc} 0000000&0000001&0000010&0000011&0000100\\ 0000101&0000110&0000111&0001000&0001001\\ 0001010&0001011&0001100&0001101&0001110\\ 0001111&0010000&0010001&0011000&0011110\\ 0011111&0100000&0100001&0100010&0100011\\ 0101000&0101111&0110000&0110001&0111000\\ 0111100&0111101&0111110&0111111&1000000\\ 1000001&1000010&1000011&1000100&1000101\\ 1000110&1000111&1001000&1001111&1010000\\ 1010001&1011000&1011110&1011111&1100000\\ 1100001&1100010&1100011&1101000&1101111\\ 1110000&1110001&1111000&1111001&1111010\\ 1111011&1111100&1111101&1111110&1111111 \end{array} \end{align*}

Note: I've written some lines of code in R in order to check the coeffcients and generate valid words.

############################################################################
#
#  MSE 4170314
#
############################################################################
#
#  generate all combinations of length "len"
#  of elements given in "v"
#
combinations <- function(v,len) {
  cur_v <- v
  if (len > 1) {
    for (i in 1:(len-1)) {
      next_v <- as.vector(outer(cur_v, v, paste, sep=""))
      cur_v <- next_v
    }
  }
  return(cur_v)
}
 
#
# main part
#
for (n in c(1:12)) {

   v <- c("0", "1")
   w <- combinations(v,n)
   w0  <- w[grepl("000",w)]
   w1  <- w[grepl("1111",w)]
   w_res <- sort(unique(c(w0,w1)))

   print(paste(n,length(w_res)))
   if (n == 7) {
       print(paste(w_res, collapse = "&"))
   }
}

Answer 2

I will answer part (a). Parts (b) and (c) should be done similarly.

Using the Goulden Jackson method you mention, the generating function is

$$f(s) = \frac{1}{1-2s-w},$$

where $w$ is the weight of the cluster of bad words. The bad word in our case is just $\{000\}$. We have that $w$ satisfies

$$w = -s^3 - (s^2+s)w$$

since there are two overlaps of $000$ with $000$, one of length one and one of length two.

Solving for $w$ gives $w = \frac{-s^3}{1+s+s^2}$. Plugging this in gives the generating function

$$\frac{1}{1-2s+\frac{s^3}{1+s+s^2}} = \frac{1+s+s^2}{1-s-s^2-s^3}$$

You can verify that the first few terms of the above are

$$1+2s+4s^2+7s^3+13s^4+24s^5+O(s^6)$$

and the first few terms can be verified.

Answer 3

Not using the Goulden Jackson Method:

For part (a), let $a_n$ be the number of bit strings of length $n$ with no three consecutive $0$s. Assume $n\geq 4$ (for $n=1,2,3$, we'll need to calculate manually to find the initial conditions). By the sum rule, we split the cases into three possibilities for the starting bit(s).

$$a)\ 1..$$ $$b)\ 01..$$ $$c)\ 00..$$ $$$$

In the first case, there are $a_{n-1}$ bit strings of length $n$ without $000$ that start with a $1$ (just append it to the $1$). For the second case, $a_{n-2}$.For the third case, the next bit must be a $1$, so there are $a_{n-3}$ ways there. The answer is thus

$$a_n = a_{n-1}+a_{n-2}+a_{n-3},$$

with initial conditions $a_1 = 2,a_2 = 4,a_3 = 7$.