Bits in binary strings.

[nille40]

Hi all!
I'm in serious need of some help.

The question:
How many binary strings of length 10 contains exactly two "01"?

My idea was to weld together 4 bits to 2 "01". That way, there's \frac{8!}{2!} strings with at least 2 "01". But there are a bunch of strings with more than 2 "01" in these, and these must be accounted for. How can I locate these?

Thanks in advance,
Nille

[Hurkyl]

All right, think of it this way:

Any string of "0"s and "1"s can be thought of in the following way:

It starts with some positve number of one of the digits, then it is some positive number of the other digit, then the first one again, and so on...

Any bit sequence can be represented this way, and in this representation it is easy to identify whether it satisfies your constraint (exactly two occurences of "01")...

Once you do this, can you figure out how to count them?

[nille40]

Hi! Thanks for responding!

You seem to be on to something, there... I don't understand it though...

The answer is this (not my solution):
First there's a string of 1:s, of length x_1, then a string of 0:s, x_2, x_3 1:s, x_4 0:s, x_5 1:s, and finally x_6 0:s. The part with x_2 0:s and x_3 1:s garantuees a "01", and the part with x_4 0:s and x_5 1:s garantuees the next "01". Since the length is supposed to be 10, this yields the equation

x_1+x_2+x_3+x_4+x_5+x_6=10

The x_1 first 1:s and the x_6 last 0:s is just filling (??). Another way to put it is the number of integral solutions the equation has. By letting x_2 = y_2 + 1, x_3 = y_3 + 1, x_4 = y_4 + 1, x_5 = y_5 + 1, we get the equation

x_1 + y_2 + y_3 + y_4 + y_5 + x_6 = 6

and the problem can be stated as the number of integral solutions to the above equation. According to the formula for unorganized selection with repetition, the number of solutions is

{11 \choose 5}

English isn't my native language, so the lingo might be wrong. I hope it's not to fuzzy.

To be honest, I don't understand one single thing of this! This is really frustrating and I really, really hope someone can help me.

Thanks in advance,
Nille

[Hurkyl]

That answer is the direction in which I was trying to point you.

What parts of it don't you understand?

[nille40]

Hmm... I think I'm beginning to understand this now...

Its impossible to model a sequence of more than two "01" with the equation

x_1 + \underbrace{x_2 + x_3 + x_4 + x_5}_{\ge 1} + x_6 = 10

This I understand, pretty well. The next step though, is somewhat a mystery to me. I've realized that the formula used is
{n+r-1}\choose{n}

But can't this formula be applied directly to the equation. Why the substitution x_2 = y_2 + 1, x_3 = y_3 + 1 etc?

And finally: where can I get more information about the formula? It's not part of the litterature I'm using.

Thank you very much for helping me!
Nille