1
$\begingroup$

How many binary numbers of length $n$ can be generated where $n > 7$ and the number either start with $000$ or end with $111$?

My questions is, can I choose an $n$ randomly? For example, let's say that $n = 8$. Since the first three terms need to be $0$, they can have only one option and the remaining five digits can be $0$s or $1$s meaning that they have two options. The same identity applies for the ending with $111$ case.

So my guess is, $2^5+2^5 = 32+32 = 64$

Is this answer correct? By the way forgive me if I couldn't explained my answer clearly, thanks..

$\endgroup$
  • $\begingroup$ you forgot to take into consideration, that n>7... $\endgroup$ – V-X Oct 13 '14 at 19:35
  • $\begingroup$ I did not forget, i chose 8 as n. What do do you mean by that, couldn't see your point :) $\endgroup$ – odd Oct 13 '14 at 19:36
  • 2
    $\begingroup$ You have counted the numbers of form $000xy111$ twice. $\endgroup$ – Antoine Oct 13 '14 at 19:36
  • 2
    $\begingroup$ Use the fact that $|A\cup B|=|A|+|B|-|A\cap B|$ $\endgroup$ – Peter Franek Oct 13 '14 at 19:38
  • 2
    $\begingroup$ The answer should be given as a function of $n$. $\endgroup$ – barak manos Oct 13 '14 at 19:40
4
$\begingroup$

there is $$2^{n-3}$$ numbers of length n with 000 at the beginning and there is $$2^{n-3}$$ numbers of length n with 111 at the end. also there is $$2^{n-6}$$ numbers that has both 000 at the beginning and 111 at the end, thus the result is $$2 * 2^{n-3} - 2^{n-6} = 15 * 2^{n-6}$$ numbers corresponding your conditions...

$\endgroup$
1
$\begingroup$

Inclusion/Exclusion:

The amount of $n$-digit numbers that start with $000$ is $2^{n-3}$

The amount of $n$-digit numbers that end with $111$ is $2^{n-3}$

The amount of $n$-digit numbers that start with $000$ and end with $111$ is $2^{n-6}$

The amount of $n$-digit numbers that start with $000$ or end with $111$ is $2^{n-3}+2^{n-3}-2^{n-6}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.