## anonymous 5 years ago how many bit strings length 9 contain exactly 3 ones?

1. anonymous

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)!}$

2. anonymous

so would the answer be 42?

3. anonymous

how did you come to that?

4. anonymous

i plugged in 9 for n and 3 for k

5. anonymous

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

6. anonymous

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

7. anonymous

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

8. anonymous

9. anonymous

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

10. anonymous

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.

11. anonymous

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.