2
$\begingroup$

Given a bit string $x$ of length $n$, how many strings are there that differ from $x$ in exactly $k$ positions?

Also, if we replaced the case with decimal strings, how would it change?

I'm a bit stuck. I'm not sure which method to use to solve this question. I'm between whether to use regular permutation, or difference method, but both of those could still be incorrect.

Any insight would be helpful, thank you!

$\endgroup$
3
  • 2
    $\begingroup$ Your question should be clear without the title. After the title has drawn someone's attention to the question by giving a good description, its purpose is done. The title is not the first sentence of your question, so make sure that the question body does not rely on specific information in the title. $\endgroup$ – Martin R Jul 20 '19 at 16:09
  • 1
    $\begingroup$ How many ways can you choose $k$ positions from the available $n$ positions? $\endgroup$ – AgentS Jul 20 '19 at 16:16
  • 1
    $\begingroup$ Think of it like choosing $k$ positions to flip the bits $\endgroup$ – AgentS Jul 20 '19 at 16:18
1
$\begingroup$

Given a bit string of length $n$, how many strings are there that differ from $x$ in exactly $k$ positions.

Strategy:

  1. Choose which $k$ of the $n$ positions differ from the original bit string.
  2. In each place where the original bit string had a $0$, it must be replaced by a $1$; in each place where the original bit string had a $1$, it must be replaced by a $0$.

Given a decimal string of length $n$, how many strings are there that differ from $x$ in exactly $k$ positions.

Strategy:

  1. Choose which $k$ of the $n$ positions differ from the original decimal string.
  2. Choose which of the other nine decimal digits replaces the number in each of the $k$ positions where the new string differs from the original string.
$\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.