# Finding how many bits of length n there are

So we are starting on the section of combinatorics in my discrete math class and our instructor gave us a simple problem to see if we understood what we learned that day. The problem consists of three parts.

Problem:

3.)

A.) How many bit strings of length eight are there?

B.) How many bit strings of length eight are there with exactly two zeroes?

C.) Let n > 2 be а positive integer. How many bit strings of length n are there with exactly two zeroes?

Work:

Part A is relatively simple. Since a bit consists of either the number 1 or 0, there are only two ways that the first slot can be filled or ${2^n}$ ways. Since there are eight bits, the answer would be ${2^8}$ or 256.

Part B is also relatively simple. There are a number of ways to solve this one. One way is to realize that is that you can fill up seven slots with two zeros, then 6 and so on (7 + 6 + 5....+ n-1). The end result is 28.

Part C to me is a little bit tricky. Part C is almost the same as part B but it's asking about ${n}$ strings. So what I could do is expand my work from part B. The symbol ${n}$ represents the length of the bit string. So for example, if we have a 3 bit string, we have 3 slots to fill and 3! ways to fill each slot. 2! of those slots have to be filled with a zero. Then we can generalize for any bit string having exactly 2 zeros by the equation: ${\frac{n!}{2!(n-2)!}}$.

Is all of my work correct?

Edit: Just fixed a couple of errors.

• The answers are all correct. The explanations in 2) and 3) are not as clear as they might be. Have you been introduced to the binomial coefficient $\binom{n}{k}$ ("$n$ choose $k$")? – André Nicolas Jul 11 '15 at 15:45
• @AndréNicolas I think we are going to start on the binomial theory on Monday and how you can relate it to combinatorics – Deathslice Jul 11 '15 at 15:48
• If binomial coefficients have not yet been covered, it would be good to make your reasoning, which is undoubtedly correct, more explicit. – André Nicolas Jul 11 '15 at 16:08

Your answers are all correct, your expression for number $3$ can be easily reduced to $\frac{1}{2}(n-1)n$.
That formula can also be obtained directly, let's say you have $n$ bits, you have to choose $2$ of them that will be $0$, the first can be chosen in $n$ ways, since you can pick any of the bits, while the second one can be chosen in $n-1$ ways, since you cannot choose the same bit twice, that gives a total of $n(n-1)$ ways. You have to divide by $2$ because the $0$s are indistinguishable so putting the first $0$ in the $5$th bit and the second $0$ in the $10$th bit is the same as putting the first $0$ in the $10$th bit and the second $0$ in the $5$th bit
Another way to realize this is to let $z$ mean "zero", $o$ mean "one" and to use the binomial theorem:
$$(z+o)^n = \sum_{k=0}^{n} \left(\begin{array}{c}n\\k\end{array}\right)z^ko^{n-k} = \sum_{k=0}^{n}\frac{n!}{k!(n-k)!} z^ko^{n-k}$$
the exponents arithmetically will become the numbers of $z$ and $o$ picked and the coefficients will be the combinations.This also allows for "encoding" probabilities into the calculations. Say that any one has double probability as that of a zero, we could evaluate $(z/3+2o/3)^n$. We would need to "normalize" (divide) with $2^n$ to get probabilities in the answer, though.