3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$")? $\endgroup$ – André Nicolas Jul 11 '15 at 15:45
  • $\begingroup$ @AndréNicolas I think we are going to start on the binomial theory on Monday and how you can relate it to combinatorics $\endgroup$ – Deathslice Jul 11 '15 at 15:48
  • $\begingroup$ If binomial coefficients have not yet been covered, it would be good to make your reasoning, which is undoubtedly correct, more explicit. $\endgroup$ – André Nicolas Jul 11 '15 at 16:08
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Bravo, a much better explanation. $\endgroup$ – Deathslice Jul 11 '15 at 15:55
0
$\begingroup$

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.

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