The Problem
I've been self-studying Introduction to Analysis of Algorithms by Sedgewick and Flajolet. I'm on the fifth chapter, and struggling with exercise 5.1:
How many bit strings of length N have no 000?
More specifically, the authors want a closed form expression counting the number of bit strings of length N which have no 000 as a substring.
My Plan of Attack
I believe the authors intend the problem to be solved in these steps:
- Find an "Analytic Combinatorial" expression for the problem statement
- Convert the aforementioned expression into a generating function
- Find a corresponding series for the generating function; in particular, find a closed form for the coefficients
The closed form for the coefficients will give me the answer I seek. I believe I have either:
- found a needlessly complicated analytic combinatorial expression, or
- do not understand generating functions enough to solve the generating function
My Work Thus Far
The Analytic Combinatoric Expression
I arrived at this form for the generating function:
$$ \mathcal{G} = \varepsilon + \mathcal{Z}_0 + \mathcal{Z}_0 \times \mathcal{Z}_0 + (\mathcal{Z}_1 + \mathcal{Z}_0 \times \mathcal{Z}_1 + \mathcal{Z}_0 \times \mathcal{Z}_0 \times \mathcal{Z}_1) \times \mathcal{G} $$
I've used Sedgewick and Flajolet's notation where $\mathcal{G}$ corresponds to the set in which I'm interested, $\mathcal{Z_x}$ corresponds to the singleton set containing the object $x$, and $\varepsilon$ is a "neutral object of size zero".
I justify this expression as follows. Strings that don't have three consecutive zeros can have three different configurations of their three leading bits:
- $001$
- $01X$
- $1XX$
I've used $X$ to indicate either $0$ or $1$.
Therefore, any shorter string not containing three consecutive zeros can be extended by prepending either $1$, $01$, or $001$.
I also add $0$ and $00$ since I cannot generate them using the previously mentioned scheme.
I confirmed that I can generate all length three strings except $000$ using this analytic combinatoric expression:
- $101 = 1 \cdot 01 \cdot \varepsilon$
- $100 = 1 \cdot 00$
- $011 = 01 \cdot 1 \cdot \varepsilon$
- $010 = 01 \cdot 0$
- $111 = 1 \cdot 1 \cdot 1 \cdot \varepsilon$
- $110 = 1 \cdot 1 \cdot 0$
- $001 = 001 \cdot \varepsilon$
The Generating Function
From the analytic combinatoric expression I derived this generating function:
$$ G(z) = \frac{1 + z + z^2}{1 - z - z^2 - z^3} $$
And this is where I've become quite stuck. AFAIK, the denominator, $1 - z - z^2 - z^3$ does not have any "simple" roots. I'd really like to factor it into a series of binomials of the form $(1 - cz)$ so that I can apply some of the ordinary generating functions machinery we studied in chapter three.
Being analytically stuck, I turned to Wolfram Alpha which helpfully points out that the full expression has two simple roots:
$$ -\sqrt[3]{-1} $$ and $$ (-1)^{2/3} $$
I don't know their multiplicity. I thought about writing the expression as:
$$ (1 - z(-1)^{-1/3})(1 - z(-1)^{-2/3}) $$
But I don't know how to apply generating function machinery to this expresion.
Wolfram Alpha also points out that the Taylor series expansion at 0 is:
$$ 1 + 2z + 4z^2 + 7z^3 + 13z^4 + O(z^5) $$
Which lead me to try directly computing the Taylor series of the generating function. I didn't see any obvious pattern in the derivatives, but perhaps I missed something. It seemed like I was headed for a huge mess of fractions.
Conclusion
I'd really like a confirmation that the generating analytic combinatoric expression I derived is correct. I'd also really appreciate some pointers about calculating the series corresponding to my generating function.
Thanks!