Section 10.1 Counting strings
In the last chapter, we have established how to count each of the four common types of binary samples: those with and without order, and those with and without replacement. In this chapter, we will explore some of the powerful and surprising theorems that arise regarding the binomial coefficients, that is, the numbers of unordered samples without replacement.
Indeed, we have already seen one such example. By realizing that an unordered sample with replacement can be represented as a bit string with a fixed number of zeros, we can use a binomial coefficient to count that type of sample as well. Therefore, we will begin this chapter by explicitly considering how binomial coefficients count binary strings with a fixed number of zeros (or equivalently, a fixed number of ones). Then, we will explore some identities that arise from this viewpoint.
By the way, it is perfectly good to think about counting subsets instead of counting bit strings. However, it seems to be the case that students prefer the concreteness of bit strings as opposed to the abstractness of sets.
Definition 10.1.1.
The number
is called a binomial coefficient.
We will understand the reasoning behind this choice of terminology shortly.
In the last chapter, we learned that binomial coefficients count the number of \(r\)-element subsets of a \(n\)-element universe. By combinatorial proof, we immediately were able to conclude that binomial coefficients also count the number of bit strings with a fixed number of ones (or a fixed number of zeros).
Because it will be very important in the remainder of this chapter, let's explicitly enumerate the bit strings with five digits and see what patterns arise. This example will reoccur throughout the chapter, so make sure you understand it.
Example 10.1.2.
By the multiplication rule, there are \(2^5=32\) total five-digit bit strings (because every digit can be either a 1 or a 0, and the choices are independent).
First, there is a single bit string with no ones: the string \(00000\text{.}\) Let's confirm that the corresponding binomial coefficient counts this object:
Next, there are five bit strings with a single one: \(10000\text{,}\) \(01000\text{,}\) \(00100\text{,}\) \(00010\text{,}\) \(00001\text{.}\) Once again,
(Notice how we use the factorial's recursive property, \(n! = n(n-1)!\text{,}\) to calculate the binomial coefficient.)
There are going to be ten bit strings with two ones. They are \(11000\text{,}\) \(10100\text{,}\) \(10010\text{,}\) \(10001\text{,}\) \(01100\text{,}\) \(01010\text{,}\) \(01001\text{,}\) \(00110\text{,}\) \(00101\text{,}\) \(00011\text{.}\) Furthermore,
We could continue on and enumerate the number of strings with three ones, or we could take a moment to notice something. A string with three ones is just a string with two ones where we swap the ones and the zeros. For example, the string \(11010\) corresponds in this way to the string \(00101\text{.}\) Therefore, there are also ten strings with three ones because of this duality:
Observe that the order of the \(2!\) and \(3!\) in the denominator does not affect the result.
The following table summarizes our results.
\(r=0\) | \(00000\) | \(\displaystyle {{5}\choose{0}} = \frac{5!}{0!5!} = 1\) |
\(r=1\) | \(10000\text{,}\) \(01000\text{,}\) \(00100\text{,}\) \(00010\text{,}\) \(00001\) | \(\displaystyle {{5}\choose{1}} = \frac{5!}{1!4!} = 5\) |
\(r=2\) | \(11000\text{,}\) \(10100\text{,}\) \(10010\text{,}\) \(10001\text{,}\) \(01100\) | \(\displaystyle {{5}\choose{2}} = \frac{5!}{2!3!} = 10\) |
\(01010\text{,}\) \(01001\text{,}\) \(00110\text{,}\) \(00101\text{,}\) \(00011\) | ||
\(r=3\) | \(11100\text{,}\) \(11010\text{,}\) \(11001\text{,}\) \(10110\text{,}\) \(10101\) | \(\displaystyle {{5}\choose{3}} = \frac{5!}{3!2!} = 10\) |
\(10011\text{,}\) \(01110\text{,}\) \(01101\text{,}\) \(01011\text{,}\) \(00111\) | ||
\(r=4\) | \(11110\text{,}\) \(11101\text{,}\) \(11011\text{,}\) \(10111\text{,}\) \(01111\) | \(\displaystyle {{5}\choose{4}} = \frac{5!}{4!1!} = 5\) |
\(r=5\) | \(11111\) | \(\displaystyle {{5}\choose{5}} = \frac{5!}{5!0!} = 1\) |
Because there are 32 strings total, it must be the case that
In the next section we will expand on some of the things we noticed in this example.