Probability of Non-Adjacent Zeros in 11-Digit Integer with 1 and 0 Digits

[Raghav Gupta]

I'm trying to get you to express the answer to my question using the $f_n$ sequence.
By definition, the number of ways of filling in n-1 digits with no two adjacent zeroes is $f_{n-1}$. Pretend that you knew this number. Suppose it's 999. Now you have n digits to fill in. You fill in the first as a 1, say. How many ways of filling in the rest?

But that's difficult finding the ways of filling in the rest.
Though there may be another way but we can generalize pattern

$f_1 = 2$ 0 and 1
$f_2 = 2^2-1$ each place has two options and the 00 case has to be subtracted.
$f_3 = 2^3-3$ 001,100,000 removed
It keeps getting complicated.

$f_4= 2^4-8$
$f_n = 2^n-some pattern$
That pattern is finding nth term for sequence
0, 1, 3, 8, 16, 27------

 

[AdityaDev]

Got it...
$f_n$ starting with zero is equal to $f_{n-2}$
$f_n$ starting with one is equal to $f_{n-1}$
So $f_{n}=f_{n-1}+f_{n-2}$

 

[Raghav Gupta]

Got it...

So $f_{n}=f_{n-1}+f_{n-2}$

It's like fibonacci seq.
How you'll find f_n-1 and f _n-2

 

[AdityaDev]

$f_n=f_{n-1}+f_{n-2}$
$f_{n-1}=f_{n-2}+f_{n-3}=f_{n-3}+2f_{n-4}+f_{n-5}=...$ coefficients are part of pascals triangle.
$f_{n-2}=f_{n-3}+f_{n-4}$

 

[Raghav Gupta]

So in your question there are 10 spaces but if it would have been more then it would be a lengthy process?

 

[AdityaDev]

If r denotes the number of steps, fn=fn-1+fn-2
r=2, fn=fn-2+2fn-3+fn-4
For r=r, $f_n=f_{n-r}+ \binom{r}{1}f_{n-r-1}+ \binom{r}{2}f_{n-r-2}+ ...$

 

[Raghav Gupta]

If r denotes the number of steps, fn=fn-1+fn-2
r=2, fn=fn-2+2fn-3+fn-4
For r=r, $f_n=f_{n-r}+ \binom{r}{1}f_{n-r-1}+ \binom{r}{2}f_{n-r-2}+ ...$

Well it would take me much time to understand that in correlation with your problem but I guess you have reached the answer?

 

[AdityaDev]

Well it would take me much time to understand that in correlation with your problem but I guess you have reached the answer?

No. I am waiting @haruspex to check If its correct.

 

[haruspex]

Got it...
$f_n$ starting with zero is equal to $f_{n-2}$
$f_n$ starting with one is equal to $f_{n-1}$
So $f_{n}=f_{n-1}+f_{n-2}$

Bingo!

 

[AdityaDev]

Bingo!

Whats the next step?

 

[Raghav Gupta]

I am excited on finally solving up your question.
It has been a lengthy thread.
Your attempt was on a right track but a few mistakes there.
I don't know why @haruspex brought you on a recurrence relation which is not taught in high school.
Maybe different thinking patterns.

Homework Statement

Consider a 11 digit positive integer formed by the digits 1,0 or both. The probability that no two zeros are adjacent is:

The Attempt at a Solution

First digit has to be 1.

Total number of permutations=2¹⁰

Now 1XXXXXXXXXX is the format.
Taking 10 digits starting from 2nd digit, it has to be like 01X1X1X1X1 or it has to be like 1X1X1X1X1X.
(X can be 0 or 1).

For first case if I take one zero, it can be place in any of the 4 X = 4C1
If I take 2 zero, 4C2 and so one because the other X has to be filled by 1.

First case: 4c1+4c2+...+4c4=16
Second case:5c1+...5c5=32

Hence probability = (2⁴+2⁵)/2¹⁰=3/64.
But answer is 9/64

First digit is obviously 1. Now considering all things from 2nd digit onwards.
When we have no zero in number then we have 10 ones and obviously that is one way.
When we have one zero in number then we have 9 ones.
Placing ones at alternate places.
_1_1_1_1_1_1_1_1_1_.
We have 10 spaces and one zero to place in any space, so number of ways = 10_C1
When we have 2 zero in number then we have 8 ones
Placing ones at alternate places.
_1_1_1_1_1_1_1_1_
We have nine spaces and two zeroes to place in any space, so number of ways = 9_C2= 36.
I hope you get the pattern and maximum zeroes we can have is 5.
Any further queries?

 

[AdityaDev]

The answer 118/2^11 is not correct.

 

[Raghav Gupta]

The answer 118/2^11 is not correct.

Where I have written that answer?

 

[Raghav Gupta]

The answer 118/2^11 is not correct.

To whom you are referring?

 

[AdityaDev]

From post 41. I tried calculating.

 

[AdityaDev]

Haruspex dissapeared. He left me confused. I don't know how to proceed.

 

[Raghav Gupta]

But I am getting 144/2¹⁰.
Which is 9/64.
Have you read my post 41 carefully.
What would be the ways of creating numbers having non adjacent zeroes when we have 3 zeroes.?
Are you following my pattern? It's easy.

 

[Raghav Gupta]

The answer 118/2^11 is not correct.

I am getting both numerator and denominator different finally. I have given hints in 41. Do you understand?
Why 2¹¹ in denominator. It would be 2¹⁰ as we have 10 spaces as obviously first digit is 1.

 

[AdityaDev]

But I am getting 144/2¹⁰.
Which is 9/64.
Have you read my post 41 carefully.
What would be the ways of creating numbers having non adjacent zeroes when we have 3 zeroes.?
Are you following my pattern? It's easy.

10C1+9C2+8C3+7C4+6C5

 

[Raghav Gupta]

10C1+9C2+8C3+7C4+6C5

Yeah, I think you got it.

 

[Raghav Gupta]

So can we say you have understood and got the answer?

 

[haruspex]

That pattern is finding nth term for sequence
0, 1, 3, 8, 16, 27------

The last two terms are wrong, should be 19 and 43.

Haruspex dissapeared. He left me confused. I don't know how to proceed.

hey, I have to sleep sometime. (7:30am here now.)
Having got the recurrence relation, it is a trivial matter to work through from the smaller numbers:
f₀=1, f₁=2, so f₂=1+2=3, etc. up to f₁₀=144.
As to whether this method is too 'advanced', I would not have thought so. You don't need to know it is called a recurrence relation, and you don't need to solve the relation (i.e. find a general formula for f_n). It's more like applying induction. You need to spot that having filled in the first digit the problem for the remaining digits hasn't changed much.

The 10C1+8C3+... method is fine too. It involves rather more calculation though. If you spot the recurrence method, it's much easier.

 

[AdityaDev]

hey, I have to sleep sometime. (7:30am here now.).

we are in different timezones then. My 2:22 am is your 7:30 am!

 

[Raghav Gupta]

10C1+9C2+8C3+7C4+6C5

There should be 11_C0 term = 1 also considering no zeroes in number.

Having got the recurrence relation, it is a trivial matter to work through from the smaller numbers:
f₀=1, f₁=2, so f₂=1+2=3, etc. up to f₁₀=144.
As to whether this method is too 'advanced', I would not have thought so. You don't need to know it is called a recurrence relation, and you don't need to solve the relation (i.e. find a general formula for f_n). It's more like applying induction. You need to spot that having filled in the first digit the problem for the remaining digits hasn't changed much.

But how you got f₁₀ fast? It would take time to add that numbers starting from f₀ unless you use a software.
It's like fibonacci series where there are no first two terms 0, 1.
I think you may have applied Binet's formula? But it is also lengthy, considering the powers and not using calculator.

Haruspex left me. He made me confused that how to proceed.

How you know that Haruspex is he/she.
According to wikipedia-Haruspex

 

[AdityaDev]

How you know that Haruspex is he/she.
According to wikipedia-Haruspex

That does not matter. I got my doubt cleared and I am happy. Even if haruspex is a she.. what difference does it make?

 

[Raghav Gupta]

I was just joking.
But how we get f₁₀ fast? Do we have to add all terms starting from f₀

I got my doubt cleared and I am happy

I think you meant question and not doubt.

 

[haruspex]

But how you got f₁₀ fast? It would take time to add that numbers starting from f₀ unless you use a software.
It's like fibonacci series where there are no first two terms 0, 1.

f(0) = 1, f(1) = 2 easy
after that
1+2=3
2+3=5
3+5=8
5+8=13
8+13=21
13+21=34
21+34=55
34+55=89
55+89=144
Done. Isn't that simpler than working out all those combinatorial functions? But I suppose you used an app/spreadsheet for that.
It might not be obvious to you that f(0)=1, so start with f(1) and f(2) by hand instead.

One benefit of my approach is that it scales. You can easily deduce the asymptotic behaviour.
Putting the two approaches together yields an interesting result about the sum of a combinatorial series.

 

[Raghav Gupta]

Thanks, I learned other approach but what if there were more spaces instead of 10. Now should we use Binet's formula? In software we can make loops for calculating that nth term for a recurrence relation and here it's easy because there were only 10 spaces.
In my approach there is a sequence for finding nth term.

 

[haruspex]

Thanks, I learned other approach but what if there were more spaces instead of 10. Now should we use Binet's formula? In software we can make loops for calculating that nth term for a recurrence relation and here it's easy because there were only 10 spaces.
In my approach there is a sequence for finding nth term.

Even if there's no effort obtaining the combinatorial terms in your series, you still have to add n of them (or n/2, maybe). Using Fibonacci, you have to add n terms, but no combinatorials to calculate.
Ultimately, Binet may be fastest. You'd have to round to nearest integer, but I'm sure you could go a long way before that might go wrong.

 

[Raghav Gupta]

Yeah that's true, I agree with you. Ultimately it comes to the person in the first place how to originate approach from his mind.
I never have seen that approach by anyone in my school and it's a kinda gem for me.