The number of strings of length five consisting of 0's and 1's with no consecutive 1's are ?

Question

terenzreignz · Answer

Oh counting problems... 
Let me think...

anonymous · Answer

yup sure

terenzreignz · Answer

How are you supposed to do this, though? Recurrence relations?

anonymous · Answer

I was thinking to do this through permutations and combinations !

terenzreignz · Answer

Silly me... recalculating :3

terenzreignz · Answer

Okay, so, obviously, the total number of strings if you do not add restrictions is $\large 2^n$ right?

terenzreignz · Answer

err.. $\large 2^5 = 32$ to be specific..

anonymous · Answer

yup

terenzreignz · Answer

Maybe there's a way to count all 'forbidden' strings?
The ones which contain consecutive 1's.

anonymous · Answer

yeah i was thinking to do like that, around the way by subtracting the total no. of strings consisting of consecutive 1's frm the 2^5 strings, but cudnt start how to do tht !

terenzreignz · Answer

Yeah, it's tricky... wrong methods result in double counting... hmmn...

terenzreignz · Answer

Brute force, then?

anonymous · Answer

can we do it like taking number of string numbers as 4 with 11 taken as only one place

terenzreignz · Answer

After all, it's only a string of length 5...

anonymous · Answer

2^5-2^4 is that the correct way ?

terenzreignz · Answer

See, that's the problem, moli1993 (name pls lol)
You could certainly try placing a fixed 11 on one of the four possible places you could put it... however
say you do this...
count
11???
?11??
??11?
???11

You'll be counting the combination 
1111 *twice*
which will screw up your calculations XD

terenzreignz · Answer

11110*

anonymous · Answer

LOL name is Mallika :p
my bad

terenzreignz · Answer

TJ.
Pleasure :)


Anyway, at least let's arrive at the correct answer before we try anything fancy.
Take cases.
Obviously, we cannot allow strings with 4 or 5 1's in it, there's no way to arrange them without having consecutive 1's

If there's only one 1, how many length-5 strings are allowable?

anonymous · Answer

ummm , I didnt get u actually how the cases are repeated if i considr it as 4 place string with consecutive 1 i.e 11 taken as a single place

terenzreignz · Answer

Okay, let's do that ^_^
We arrange a 11, 0's and 1's on four places, yeah?
So, that means we permute the 0's and 1's first, and then place the 11 on one of the four possible places to put it...

Effectively rendering the number $\large 2^3 \cdot 4 $ or $\large 2^4$

terenzreignz · Answer

or wait, sorry, $\Large 2^3 \cdot 4 = 2^5$
Well then.. :3

terenzreignz · Answer

So we arrive at $\large 2^5$ the total number of arrangements when there are no restrictions... so either there's no way to arrange a string of 5 bits (0's and 1's) without having consecutive 1's... OR we counted some stuff twice ;)

anonymous · Answer

ohk got it (Y) then

terenzreignz · Answer

Bear with me... no fancy counting methods until we know what we're actually shooting for :)

If there's only one 1, how many string of 5 bits are possible?

anonymous · Answer

one only

terenzreignz · Answer

nope.
There are 5.
10000
01000
00100
00010
00001

anonymous · Answer

ohh i thought u were saying when we have only 1 option that is only 1 is the digit to fill all the 5 places, my bad , ya 5 ways !

terenzreignz · Answer

Okay, what if there are two 1's?
How many possible (and allowable!) five-bit strings do we get?
Think on it now...

anonymous · Answer

ohk wait , lemme think

anonymous · Answer

by allowable u mean , no  2 consecutive 1's ?

terenzreignz · Answer

Yup.

anonymous · Answer

ohk

anonymous · Answer

10100
10010
10001
01001
01010
00101
6 ways ?

terenzreignz · Answer

6 ways, yes.
Now what about with three 1's?

anonymous · Answer

10101
only 1 way?

terenzreignz · Answer

that's right, lol

And that's all of them... riiiight? :D

anonymous · Answer

isn't there a formula to calculate this, this is getting lenghty !

terenzreignz · Answer

There is a way, but the only way I could think of is using recurrence relations... and you shunned those right away XD

anonymous · Answer

5+6+1= answer ?

terenzreignz · Answer

Yes... because there are no allowable strings with four or five 1's, yes?

zarkon · Answer

00000

anonymous · Answer

yeah coz consecutive 1's wud be allowed in that case which we dont want :)

anonymous · Answer

so 6+5+1+1 ? including 00000

terenzreignz · Answer

oops...
good thing there's someone else watching this o.O

My bad Zarkon <head scratch>

zarkon · Answer

this about this....

$$\sum_{x=0}^{3}{6-x\choose x}=13$$

zarkon · Answer

*think

anonymous · Answer

Oh My God zarkon , how did u come to tht formula ?

anonymous · Answer

Teren is 
5+6+1+1 is the final answer then ?

terenzreignz · Answer

it's TJ -_-

And yes, that's the final answer.

Meanwhile, I was trying to find a way to get the answer for any length n of your string.

And believe it or not, it follows a Fibonacci sequence :)

anonymous · Answer

yeah TJ :)
thank you so much !
how come fibonacci ??

terenzreignz · Answer

I'll show you.
But bear with me, it involves recurrence relations...
Suppose $\large a_n$ is the number of strings of bits of length n, where there are no consecutive 1's.... 

Catch me so far?

anonymous · Answer

yup

terenzreignz · Answer

Okay, suppose we want to find an expression for $a_n$
Then let's analyse.
$$\Large \text{_ _ _ _ ... ?}$$
A string either ends in 1 or 0, right?

anonymous · Answer

yup

terenzreignz · Answer

If it ends in 0
$$\Large \text{_ _ _ _ ... _ 0}$$
Then the rest of the string is just $\large a_{n-1}$
Since the rest of the string is just the number of allowable strings of length n-1.

If it ends in 1, however, then
$$\Large \text{_ _ _ _ ... } \color{red}0 \text{ 1}$$
the next-to last bit MUST be a zero, and then the rest, a string of length n-2, can be any such allowable string, or $\large a_{n-2}$

Since those ARE the only two cases, then we have
$$\Large a_n = a_{n-1}+a_{n-2}$$

anonymous · Answer

ohk got it , then !

terenzreignz · Answer

Not quite done yet.
We "cheat" a little.
We know a few certain "intial values"
In particular, we know how many allowable strings of length 1 and 2 there are.

Those are simply enough calculated.
length 1 are just either "0" or "1" so $a_1 = 2$
length 2 are just "00" "01" or "10" so $a_2=3$
And the rest follows your standard fibonacci whatnot
$$\Large 2,3,5,8,\color{red}{13},21,33$$
etc.
13 being the fifth, or our answer :)

terenzreignz · Answer

Crap, such fails... the last should be 34

gaaah

anonymous · Answer

huhh !!

zarkon · Answer

it is 34...you can also use 

$$\Large N(n)=\sum_{x=0}^{\text{floor}(n/2)+1}{n+1-x\choose x}$$


a little work will yield that this follows the Fibonacci sequence

terenzreignz · Answer

@moli1993 
problem? :3

anonymous · Answer

nope TJ but 34 doesnt comes in fibonacci ! that's the prob as u mentioned earlier !

terenzreignz · Answer

Yes it does... the sum of 13 and 21...

anonymous · Answer

@Zarkon  can you please explain how to concluded to this formula ?
whr did it come frm !

zarkon · Answer

I used math and derived it

anonymous · Answer

TJ, my bad , yeah u are correct !
I got it . Thanks a ton !

terenzreignz · Answer

I am ALWAYS correct.
Except when I'm wrong xD

LOL this was fun ^_^

anonymous · Answer

@Zarkon  , if time allows can u please explain how u derived it ?

anonymous · Answer

:)

zarkon · Answer

you just use a little trick over and over...


if you don't want  '11'  then you put a zero next to a 1

'10'  and you treat this as one object...then start counting  ;)

anonymous · Answer

ohk

anonymous · Answer

btw @terenzreignz  , wht is ur real name ?

terenzreignz · Answer

That's what my 'detailed profile' is for, but if you must know it here, it's
Terence Jason :D

anonymous · Answer

ohh :) thanks a ton Terence for helping me :)
I was really stuck at this question

terenzreignz · Answer

No sweat. Almost got it wrong until Zarkon pointed out the annoyingly 'devious' string 00000 XD

anonymous · Answer

ha ha , no prob !
detailed profile "IMPRESSIVE" (Y)

terenzreignz · Answer

;)
Well, if you got another counting problem, I want in on it

anonymous · Answer

ha ha seems addictive ! sure , lemme find one, !
u seem from China or Japan (guessing from ur name) am I correct ?

terenzreignz · Answer

Nope.
And Wong is so not a Japanese surname XD
(Does it even SOUND Japanese? lol Don't answer that ;) )

anonymous · Answer

umm I just thought, maybe m nt that good at guessing nationality of people through their names ! My Bad :p

anonymous · Answer

u want me to post the ques here or new ques, coz here u wont be able to get the medal , coz the best response is already chosen

terenzreignz · Answer

I don't care for medals that much, but I do hate lag.
The longer this thread gets, the more lag.

Though I don't really mind it that much...

anonymous · Answer

ohk i will start with a new question !