So again, very simple constructions, immediate transfer to GF equations.

And then it's just going to be a matter of extracting coefficients.

[COUGH] So here's now first example

of a problem that might be more difficult to solve.

And it's representative of very general treatment that we'll do in Chapter 8.

How many N-bit minor strings have no two consecutive 0s?

Actually, there's lots of practical applications,

where such questions are quite important for looking for lots of consecutive 0s,

some types of communications devices have problems in such situations,

and you'd have codes that don't do that.

And so these things are well studied.

And this is a simple example, but it gets to be a much more complicated very soon.

That's what we'll talk about in Chapter 8.

But still, let's take a look at solving this with the symbolic method.

Okay, so it's the same, it's binary string, so it's the same set-up.

Our class is the class of binary strings that don't have any 00.

We have the same set-up for generating function, and the atoms are all the same.

So what does the construction look like?

Well, a binary string with no 00 is either empty or at 0,

or it's 1 or 01, followed by a binary string with no 00.

You can check if that's a way to describe the class.

You have to think about it a little bit, but it's not too bad.

And what's important, though, is that we don't have just in English language

description, we have a combinatorial construction.

Combinatorial construction immediately translates to a generating

function equation.

See 0 cross Z1 is Z squared, Z1, our generating function is Z.

At + Z0, generating function is 1+z.

So put all that together, now we have a generating function equation for

B00(z) that we can solve, and that's 1+z / 1-z- z squared.

And again [COUGH] extracting coefficients,

now these are problems that we know how to solve.

In this case, it turns out, and we'll look at the details later,

in this case, it turns out to be Fibonacci numbers.

1 / 1-z-z squared is Fn.

Z is F / 1-z-z squared is Fn+1.

If you add Fn to n+1, you get Fn+2, and that checks with the anti-Fibonacci

number, checks with the numbers that we found on the previous slide.

Many of you probably noticed that it was Fibonacci numbers at that point.

And it's clear that this argument, and this process is going to extend easily for

binary strings with other kinds of restrictions.

The trick is coming up with a construction that precisely describes your class, but

often, that's not difficult.

And again, we'll look at a general treatment of this later on in the course.