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.
Best Answer
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