0
$\begingroup$

I am just having a lot of trouble identifying this question as a combination question, and knowing exactly what numbers to use.

How many bit strings of length 10 contain?

a) exactly four 1s.

I'm comparing it to a question that I KNOW was a combinations question and that I did correctly, but I don't see how they are similar at all. The question I'm comparing it to is as follows:

In how many ways can a set of five letters be selected from the English alphabet? Because it is asking for a SET, it means order does not matter and it is a combination question, basically asking how many 5-combinations of a set of size 26 can there be.

I feel like since both answers involve combinations, I should be able to apply some sort of similar logic but I really just do not know how to approach the first problem.

Comparing my original question to the second one, I feel like it's asking for how many ways can a set of 10 bits be selected from...all possible bits? Or something? I really just do not understand what my thought process is supposed to be. The word "exactly four" is really throwing me off as well, and I just am really having trouble visualizing what it is that I'm supposed to be doing

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

A bit string of length $10$ contains $10$ bits. To build such a string so that it has exactly four $1$’s, you must decide which $4$ of the $10$ positions in the string will contain the $1$’s; once you’ve chosen those, you know that the remaining $6$ positions will contain $0$’s, so you’ve completely determined the string. Counting the $10$-bit strings with exactly four $1$’s is therefore the same as counting the number of ways to choose $4$ positions out of the $10$ possible positions; this is given by the binomial coefficient $\binom{10}4$.

The $10$ positions correspond to the $26$ letters of the alphabet. The $4$ positions that you’re choosing for the $1$’s correspond to the $5$ letters in the alphabet that you’re choosing. In each case you’re selecting a fixed size subset of some larger set: in one case a subset of size $4$ of the set of $10$ positions in the string, and in the other case a subset of size $5$ of the set of $26$ letters of the alphabet. In each case the answer to your question is simply the number of subsets of that particular size.

$\endgroup$
4
  • $\begingroup$ could I think of it like...there are 10 positions in which we could put the first 1...9 in which we could put the second 1...8 in which we could the third 1...and 7 in which we could put the fourth 1...so (10x9x8x7) and since we are only worried about 4 positions, we can divide by (10-4)!. Then we divide again by 4! because the order doesn't matter...? @Brian M. Scott $\endgroup$
    – FrostyStraw
    Commented Nov 25, 2013 at 1:43
  • $\begingroup$ @FrostyStraw: $10\cdot9\cdot8\cdot7$ should not be divided by $(10-4)!$: it already is $\frac{10!}{6!}$. The division by $4!$ is correct, however, and leaves you with $\frac{10!}{6!4!}=\binom{10}4$. You can think of it that way, but in my opinion it’s an unnecessarily complicated way of looking at it. It’s much easier just to think in terms of picking subsets of a fixed size, which are counted by binomial coefficients. $\endgroup$
    – Brian M. Scott
    Commented Nov 25, 2013 at 1:49
  • $\begingroup$ I feel like what confuses me the most is that I don't get how the fact that there are 2 possibilities (0 and 1) for every character in the string is accounted for in this case. In the alphabet question it feels like...each letter you choose can be chosen out of a set of 26, because a the set will be composed of letters out of those 26. But in the bit question, the four positions will have their values chosen from the set of bits, which is {0,1}. I'm having difficulty wording it, but it almost feels like we don't care about the possible bit characters at all. @Brian M. Scott $\endgroup$
    – FrostyStraw
    Commented Nov 25, 2013 at 1:59
  • $\begingroup$ @FrostyStraw: No, four positions will be chosen from the set of ten positions. We don’t really care about the possible characters. It would be exactly the same calculation if we wanted to know how many different sets of four digits there are, since the set of all digits is a ten-element set: in both problems we’re just counting the number of ways of picking $4$ things from a set of $10$ things. It doesn’t matter whether the things are positions in a string, digits, people (if we’re forming committees of $4$ from a pool of $10$ people), or what. $\endgroup$
    – Brian M. Scott
    Commented Nov 25, 2013 at 2:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .