I need some help with combinatorics. I have to count all the 10 bit words that contain at least 3 '1' and 3 '0', so I guess that the words would be something like this:

$$111 000 xxx x$$

The problem is that I don't really know how to determine which formula I need to use. Are these permutations with repetition, or are they variations? Becase the order is important I think that they most certainly are not combinations.

Also, I know that there are $2^n$ different 10-bit words, so there can not be more than $2^n$ such words.

  • $\begingroup$ Are you aware of the multinomial coeff.? $\endgroup$ – Studentmath Oct 7 '14 at 11:00
  • $\begingroup$ I only know how to use the binomial theorem $\endgroup$ – Mark Oct 7 '14 at 11:11

Do it by complimentary condition. How many $10$ bit words contain at most $2$ $1$s or at most $2$ $0$s?

Consider case of $0$s. The other calculation is similar.

Case 1: $0$ $0$s. Exactly $1$ such word: ${10\choose 0} = 1$

Case 2: $1$ $0$s. Choose a position for $0$: ${10 \choose 1} = 10$.

Case 3: $2$ $0$s. Choose $2$ positions for $0$s: ${10\choose 2} = 45$.

Consider same events for $1$, add those, and subtract from $2^{10}$ to get required number.

  • $\begingroup$ In fact, it is the exactly same thing, so can we just add these results $(1 + 10 + 45)$ and multiply it by $2$ and in the end get $112$, right? $\endgroup$ – Mark Oct 7 '14 at 11:16
  • 1
    $\begingroup$ Yes. Don't forget to subtract that from $2^{10}$ though. $\endgroup$ – taninamdar Oct 7 '14 at 12:01

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.