Posted on

Scrambling

OK.  I must redeem myself in the realm of counting!  Too many hasty errors on my last post for discrete math and not enough “thinking.”  Don’t fall victim to this.  And now to the question:

Q:  How many bit strings (reminder: a bit is either 0 or 1) of length 10 have:

(a) Exactly 3 zeros?
(b) Have the same number of 0 and 1
(c) Have at least 7 zeros
(d) Have at least 3 ones?

A:

(a)  Ok…  If you have a string of zeroes and ones that are 10 digits long, how many ways can you have 3 zereos and 7 ones.

Well, one way would be: 0001111111, another way would be 0010111111… etc… We don’t want to count them all out, do we?

So, we ask:  how many ways to scramble 3 zeroes and 7 ones.  First we start by asking: how many ways to scramble 10 total things?  The answer is 10! (10 factorial… that is not just an exclamation mark because I am happy).

So, there are 10! ways to scramble 10 distinct things.  However, our “things” are not distinct.  There are 3 that look alike (all zeroes) and then 7 that look alike (all ones).  We must divide out our over counts….

Overcounts:

How many ways are there to scramble three zeroes? “3!”.  How many ways are there to scramble seven ones? “7!”

Now divide out the overcounts:  10!/(3!7!) = 120 ways to have a string of three zereos and seven ones.

(b) Have the same number of zeroes and ones? This means there are 5 zereos and 5 ones.  Similar to before: 10! ways to scramble 10 distinct items, but you must divide out 5! for the five zeroes and 5! for the five ones (these are the overcounts)

10!/(5!5!) = 252 ways to have five zereos and five ones

(c) Have at least 7 zeroes? This means there could be 7 zeroes, 8 zeroes, 9 zeroes or 10 zeroes

So, 7 zeroes and 3 ones (with the same idea from a & b): 10!/(7!3!) = 120

8 zeroes and 2 ones: 10!/(8!2!) = 45

9 zeroes and 1 one: 10!/(9!1!) = 10

10 zeroes and no ones: 10!/(10!0!) = 1

So, there are 120 + 45 + 10 + 1 = 176 ways to have at least 7 zeroes.

(d) To have at least three ones?

To do this problem directly:  To have at least three ones would mean we could have 3 ones, 4 ones, 5 ones, 6 ones… all the way up to 10 ones… We need to calculate this and add it up:

(notice some of these calculations are just repeats)

3 ones and 7 zeroes = 10!/(3!7!) = 120

4 ones and 6 zeroes = 10!/(4!6!) = 210

5 ones and 5 zeroes = 10!/(5!5!) = 252

6 ones and 4 zeroes = 10!/(6!4!) = 210

7 ones and 3 zeroes = 10!/(7!3!) = 120

8 ones and 2 zeroes = 10!/(8!2!) = 45

9 ones and 1 zero = 10!/(9!1!) = 10

10 ones and 0 zeroes = 10!/(10!0!) = 1

Which equals a grand total of 968 ways.

One thought on “Scrambling

  1. Multiple ways to do some of these problems, but I just picked what I found to be the most direct.

Leave a Reply