Question

how many bit strings length 9 contain exactly 3 ones?

Answer 1

This is a combinatorics problem: another way to state this would be: how many different ways can you chose 3 things out of 9? This is often written 9C3 or "9 choose 3" and the formula for nCk is \[\frac{n!}{k!(n-k)!}\]

Answer 2

so would the answer be 42?

Answer 3

how did you come to that?

Answer 4

i plugged in 9 for n and 3 for k

Answer 5

then did 9*8*7 divided by 3*2*1

Answer 6

don't forget the (n-k)! part

Answer 7

oh i'm sorry, you're right, that should give you the right thing, but that gives you 84 i think, not 42

Answer 8

yeah your right

Answer 9

now it says show that c(9,3) = c(9,6) by describing a matching of each bit string of length 9 with 3 ones with a bit string of length 9 with 6 ones

Answer 10

when you choose 3 things from 9, you can think of that as partitioning your original set into two groups, one with 3 items and one with 9-3=6 items. In the case of this problem, one group was the set of positions that have a 1, and the other group was the set of positions that have a zero. So really, the question isn't "how many ways are there to choose 3 from 9", but more accurately "how many ways can I partition 9 things into a group of 3 and a group of 6." When you think of it in these terms, what you assign to the groups is completely arbitrary. So the number of ways to assign 3 ones and 6 zeros is exactly the same as the number of ways to assign 6 ones and 3 zeros.

Answer 11

You can check this intuition with the formula: notice that the formula doesn't care whether you plug in 9C3 or 9C6, since the two terms in the denominator just swap.