If we have a 3-bit string,

There will be 4 possible ones:


$100, 010, 001$ - one group

$110, 101, 011$ - one group


I know it is always n+1, but why?

  • 2
    $\begingroup$ If the order doesn't matter, only the number of $1$ matters. How many $1$ can there be ? $\endgroup$ – Captain Lama Apr 6 '16 at 21:38
  • 1
    $\begingroup$ So there are always $n$ spots for the 1 to go, and then we just include the string of all zeroes, which is $n+1$? $\endgroup$ – op_finales Apr 6 '16 at 21:52
  • $\begingroup$ That's pretty much it. $\endgroup$ – Captain Lama Apr 6 '16 at 21:53

community wiki post so that the question can be closed

Since the order does not matter, two binary strings are distinguished only by the number of $1$'s that occur. In a binary string of length $n$, the number of $1$'s can vary from $0$ to $n$. Therefore, as you correctly concluded, the number of distinguishable strings is $n + 1$.


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.