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

In summary: I am sorry. I am not able to understand the question.In summary, the probability of a positive integer with 11 digits formed by the digits 1, 0, or both having no two consecutive zeroes is 3/64. This is found by considering cases where there are 0, 1, 2, 3, 4, or 5 zeroes in the number and calculating the total number of possible combinations for each case.

## 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:

None

## The Attempt at a Solution

First digit has to be 1.

Total number of permutations=210

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 = (24+25)/210=3/64.

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).
There are other possibilities. E.g. ...11011011...

Edit: hint, let ##f_n## be the number of such sequences of length n (allowing leading zero); can you find a relationship between ##f_n, f_{n-1}, f_{n-2}, ..##?

Last edited:
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).
Why do you believe this? (hint ... it's not true)

(and I see haruspex beat me to it)

haruspex said:
There are other possibilities. E.g. ...11011011...

Edit: hint, let ##f_n## be the number of such sequences of length n (allowing leading zero); can you find a relationship between ##f_n, f_{n-1}, f_{n-2}, ..##?
##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
##f_3 = 2^4-7## 0001,0010,0100,1000,0000,1001,1100 has to be removed
It keeps getting complicated.

How do you find ##f_n##?

I have another approach.
Maximum number of zeroes in number would be 5 as they should not be adjacent.
Now take 5 cases.
When there are no zeroes in number you get one number where no adjacent zeroes.
When there is 1 zero in number you get 10 numbers.
When there are 5 zeroes you get 2 numbers.
Now find for cases when there is 2,3,4 zeroes

##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
##f_3 = 2^4-7## 0001,0010,0100,1000,0000,1001,1100 has to be removed
It keeps getting complicated.
No, I wasn't asking you to spot a pattern, though that could help. If you wish to pursue that, start with n=0, and your n=4 is wrong.
I was suggesting to find a general relationship between ##f_n## and its predecessors. For an n digit sequence, the first is 0 or 1. If it is 0, how many ways of filling in the remaining n-1 positions? If the first digit is 0, how many ways?

Raghav Gupta said:
I have another approach.
Maximum number of zeroes in number would be 5 as they should not be adjacent.
Now take 5 cases.
When there are no zeroes in number you get one number where no adjacent zeroes.
When there is 1 zero in number you get 10 numbers.
When there are 5 zeroes you get 2 numbers.
Now find for cases when there is 2,3,4 zeroes
There's an easier way.

haruspex said:
No, I wasn't asking you to spot a pattern, though that could help. If you wish to pursue that, start with n=0, and your n=4 is wrong.
I was suggesting to find a general relationship between ##f_n## and its predecessors. For an n digit sequence, the first is 0 or 1. If it is 0, how many ways of filling in the remaining n-1 positions? If the first digit is 0, how many ways?
In an n digit sequence, If I fix first digit as zero, then I have to find the number of ways of filling the n-1places by 0 or 1 such that no zereos are adjacent.
the second digit hast to be 1.
the third digit has 2 choices.
I am not able to find the relation.

In an n digit sequence, If I fix first digit as zero, then I have to find the number of ways of filling the n-1places by 0 or 1 such that no zereos are adjacent.
the second digit has to be 1.
the third digit has 2 choices.
OK so far. Having set the first two digits as 01, how does the number of possibilities for the remaining digits compare with ##f_{n-2}##?
What about the case where the first digit is selected as 1?

when first digit is 1, second digit is 1 or 0.
second digit 0 -> 3rd digit 1 and second digit 1 -> 3rd digit 1 or zero.

when first digit is 1, second digit is 1 or 0.
second digit 0 -> 3rd digit 1 and second digit 1 -> 3rd digit 1 or zero.
Yes, but that's not what I asked. Let's take the easier case first. If you fill in the first digit of the n as '1', how would you describe the rules for filling in the remaining digits? How does that compare with the rules for filling in the n digits (i.e. 'no two consecutive zeroes'?)
[What I'm trying to get you to find is what is called a recurrence relation. Have you ever heard of these?]

No. I don't what recurrence relation is.
If rth digit is 1, then (r-1)th digit is 0 or 1 and (r+1)th digit is also 0 or 1.
Please don't get mad if I am not able to give the answer you want. I am a little slow.

##X_{r+1}=1+X_r## if x(r) is 0.

No. I don't what recurrence relation is.
If rth digit is 1, then (r-1)th digit is 0 or 1 and (r+1)th digit is also 0 or 1.
Please don't get mad if I am not able to give the answer you want. I am a little slow.
The rule for filling in n digits is that no two consecutive digits are zero (I'm allowing a leading zero).
If you fill in the first digit of the n as '1', how would you describe the rule for filling in the remaining digits?

##X_{r+1} = X_r+1## if ##X_r## is zero.
##X_{r+1} = X_r## or ##0## if ##X_r## is 1.
##X_r## is 0 or 1.

Last edited:
Post #16# contains the rules. If the present digit x_r is 0, the 0+1 is the next digit.
if it is 1, then 1 or zero.

Post #16# contains the rules. If the present digit x_r is 0, the 0+1 is the next digit.
if it is 1, then 1 or zero.
Still not quite what I asked. I asked for the rule for filling in the remaining digits. I'm not asking for anything complicated here - it's a very simple answer.

The sum of any two adjacent digits has to to be one or two.
difference of any two adjacent digits has to be -1,0,1
Product of any two adjacent digits has to be 1 or zero.
maximum sum of all digits is n.
if you fill the sequence with x zeroes, the sum of all digits is n-x.

Rule: if there are x zeroes, then the the digits must be filled with 1s such that sum of all digits is n-x

Post #20 gives the rule.

The sum of any two adjacent digits has to to be one or two.
difference of any two adjacent digits has to be -1,0,1
Product of any two adjacent digits has to be 1 or zero.he remaining digits? Is it any differe
maximum sum of all digits is n.
if you fill the sequence with x zeroes, the sum of all digits is n-x.
You're overthinking my question.

For the full n digits, the rule is "no two consecutive zeroes".

If the first digit is a 1, what is the rule for the remaining digits? Is it any different from the rule for all n?

What if the first digit is a zero? You already noted that the second digit must be 1. So, having set the first two digits as '01', what is the rule for the remaining n-2 digits? Is it any different from the rule for all n?

Ok. If the the first digit is zero, the second digit is 1. Then the rule for fillng the n-2 digits is same as the the rule for filling n digits starting from 1.

Ok. If the the first digit is zero, the second digit is 1. Then the rule for fillng the n-2 digits is same as the the rule for filling n digits starting from 1.
What do you mean by 'starting from 1' here?

Rule for filling the remaining digits if the the number starts with digit 1.
01-------
And 1------- are the sequences.
the rule for filling -------- is same.

Rule for filling the remaining digits if the the number starts with digit 1.
01-------
And 1------- are the sequences.
the rule for filling -------- is same.
Yes!

So we define ##f_n## as the number of such sequences of n digits, for any n.
If we fill in the first digit of n digits as 1 then there are n-1 digits remaining. The rule for filling those in is the same as before, but now there are only n-1 digits. So, using our ##f## sequence, how many ways are there of filling in those remaining digits?

The rule for filling n-1digits:
the n-1 th digit can be zero or one. If it is zero, the n-2 th digit is 1 and the rule is same as that of filling digits in 01------ which will give 101-------
If the n-1 th digit is 1, then the rule is same as that of filling 1------ which will give me the sequence 11--------

The rule for filling n-1digits:
the n-1 th digit can be zero or one. If it is zero, the n-2 th digit is 1 and the rule is same as that of filling digits in 01------ which will give 101-------
If the n-1 th digit is 1, then the rule is same as that of filling 1------ which will give me the sequence 11--------
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?

If you have x zeroes and n-1-x ones, the (n-1)!/x!(n-1-x)!

If you have x zeroes and n-1-x ones, the (n-1)!/x!(n-1-x)!
No, most of those would not obey the rule.
Please try to understand the hints I'm giving you. If I make it any clearer I'll simply be giving you the answer! Your answer to my question should involve the f sequence I defined.

haruspex said:
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------

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}##

Got it...

So ##f_{n}=f_{n-1}+f_{n-2}##
It's like fibonacci seq.
How you'll find fn-1 and f n-2

##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}##

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

• Precalculus Mathematics Homework Help
Replies
2
Views
3K
• Engineering and Comp Sci Homework Help
Replies
4
Views
3K
• Calculus and Beyond Homework Help
Replies
6
Views
4K
• Calculus and Beyond Homework Help
Replies
1
Views
3K
• Calculus and Beyond Homework Help
Replies
1
Views
958
• Quantum Physics
Replies
2
Views
2K
• General Math
Replies
125
Views
17K
• Set Theory, Logic, Probability, Statistics
Replies
12
Views
3K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
0
Views
1K