2
$\begingroup$

I'm very close to solving this problem but finding the final answer is proving problematic.

A: 101x xxxx = 32 strings starting with 101 B: xxxx xx11 = 64 strings ending with 11 C: 101x xx11 = 8 strings with both of these.

The number of strings with weight five is equal to 56.

It is also important to note the number of strings starting with 101 with weight five is equal to 10 and the number of strings ending in 11 with weight five is equal to 20.

Therefore I thought the answer would've been 22 i.e. sum of 10 + 20 minus the strings common to both given this is an or problem.

$\endgroup$
4
$\begingroup$

Yes, you can use inclusion-exclusion, but the intersection should include the weight five condition. The correct count is: $$\binom{5}{3}+\binom{6}{3}-\binom{3}{1}=10+20-3=27$$

$\endgroup$
2
$\begingroup$

As you've observed:

  • There are ${5 \choose 3} = 10$ eight-bit strings of weight five starting with $101$ (your $A$)
  • There are ${6 \choose 3} = 20$ eight-bit strings of weight five ending with $11$ (your $B$)
  • These two sets overlap, so the answer to your problem is $|A| + |B| - |A \cap B|$.

But the overlap $C = A \cap B$ is the strings of the form $101xyz11$ which have five $1$s. So exactly one of $x, y, z$ is $1$, and $|C| = 3$.

$\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.