# Count the number of binary strings of size n (ORDER DOES NOT MATTER)

If we have a 3-bit string,

There will be 4 possible ones:

$000$

$100, 010, 001$ - one group

$110, 101, 011$ - one group

$111$

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

• If the order doesn't matter, only the number of $1$ matters. How many $1$ can there be ? – Captain Lama Apr 6 '16 at 21:38
• 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$? – op_finales Apr 6 '16 at 21:52
• That's pretty much it. – Captain Lama Apr 6 '16 at 21:53

## 1 Answer

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