A bit string is a string of binary digits. The binary digits are simply the numbers 0 and 1. All of the following are bit strings:
The length of the bit string is how many digits it has, and the weight of a bit string is the number of 1's it has. So \(10110\) has length 5 and weight 3. The notation for all bit strings of length \(n\) with weight \(k\) is \(\textbf{B}^n_k\). For example, the elements of \(\textbf{B}^3_2\) is 110, 101, 011.
We can manually check the length of some of small bit strings:
This seem to follow the pattern of Pascal's triangle:
Does this work for all bit strings? Consider the bit strings of length 5 having weight 3:
The first row has bit strings that starts with a 0 and the second row has bit strings that start with a 1. If we ignore the starting 0 in the first row, we see a 4-length bit string of weight 3. If we ignore the starting 1 in the second row, we see a 4-length bit string of weight 2. This means:
We can generalize this. If we want to find \(|\textbf{B}^n_k|\), we first consider all the bit strings of length \(n-1\) with weight \(k\), then add a 0 at the start (this will give \(|\textbf{B}^{n-1}_k|\) number of 5-length bit strings, all of which start with 0). Next, we consider all the bit strings of length \(n-1\) with weight \(k-1\), then add a 1 at the start (this will give \(|\textbf{B}^{n-1}_{k-1}|\) number of 5-length bit strings, all of which start with 1). Now we have all the 5-length bit strings, with their number being \(|\textbf{B}^{n-1}_{k}|+|\textbf{B}^{n-1}_{k-1}|\).
Since we know some of \(|\textbf{B}^n_k|\) follow the pattern of Pascal's triangle, then we can use induction \((|\textbf{B}^n_k| = |\textbf{B}^{n-1}_k|+|\textbf{B}^{n-1}_{k-1}|)\) to show that all \(\textbf{B}^n_k\) follow the pattern of Pascal's triangle. Therefore:
Another way to prove this is to use the formula for combination. Given \(n\) elements, there are \(n!\) ways to arrange them. If \(k\) items are the same, then we need to divide the number of ways we can arrange \(k\) elements \((n!/k!)\). Also, if \(h\) items are also the same, then we need to divide the number of ways we can arrange \(h\) elements as well:
You can read about that [here]. For a bit string having length \(n\) and weight \(k\), there are \(n\) digits, with \(k\) of them being 1's, and \(n-k\) of them being 0's. Therefore: