David W. answered • 04/01/21
Experienced Prof
What is given and what do you already know:
An 8-bit string has 8 bits (A bit is a binary digit).
A bit is either a 0 or a 1.
The weight of a bit string is the number of 1’s that it contains.
Thus, there are four 1's and four 0's.
Let's re-word the question:
How many ways can four 1's and four 0's be combined to produce an 8-bit string?
Now, remember the definitions:
A permutation is the choice of r things from a set of n things without replacement and where the order matters.
A combination is the choice of r things from a set of n things without replacement and where order does not matter.
Is this a permutation or a combination??
This is a combinations question that could be worded, "How many ways are there to select 4 letters from the 8 letters a-b-c-d-e-f-g-h? [Note: Name each of the 8 bits using a letter. Weight=4, so 'selected' letters are 1's and unselected letters remain 0's.]
So, the formula is: n! / ( (r!)*(n-r)! )
8! / (4!)*(8-4)!)
8*7*6*5*4*3*2*1 / ( (4*3*2*1)*(4*3*2*1) )
70
How many 8-bit strings have a weight of 4? 70
ADDITIONAL INFORMATION:
Pascal's Triangle (each number is the sum of the two numbers above it) gives the number of items for a two-state (i.e., heads-tails, 0-1, etc.) variable.
For example, the number of ways to get 1 head and 1 tail is 2 (see second row).
The number of ways to get:
0 ones and 8 zeros is 1
1 one and 7 zeros is 8
2 ones and 6 zeros is 28
3 ones and 5 zeros is 46
4 ones and 4 zeros is 70
5 ones and 3 zeros is 46
6 ones and 2 zeros is 28
7 ones and 1 zero is 8
8 ones and 0 zeros is 1
| 1 | 1 | |||||||||||||||
| 1 | 2 | 1 | ||||||||||||||
| 1 | 3 | 3 | 1 | |||||||||||||
| 1 | 4 | 6 | 4 | 1 | ||||||||||||
| 1 | 5 | 10 | 10 | 5 | 1 | |||||||||||
| 1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||||||||
| 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | |||||||||
| 1 | 8 | 28 | 46 | 70 | 46 | 28 | 8 | 1 |
