Combinatorics

One approach would be to figure out how many \(0\)-element subsets there are, how many \(1\)-element subsets, etc., and add up all of the values we find. This works, but there are so many pieces involved that it is prone to error. Also, the value will not be easy to calculate once \(n\) gets reasonably large.

Instead, we imagine creating a table. The columns are indexed by the elements of the set, so there are \(n\) columns. We index the rows by the subsets of our set (one per row). In each entry of the table, we place a \(1\) if the subset that corresponds to this row contains the element that corresponds to this column. Here's an example of such a table when the set is \(\{x,y,z\}\text{:}\)

As you can see, the pattern of \(1\)s and \(0\)s is different in each row of the table, since the elements of each subset are different. Furthermore, any pattern of \(1\)s and \(0\)s that has length \(3\text{,}\) appears in some row of this table.

This is not a coincidence. In general, we can define a bijection between the binary strings of length \(n\text{,}\) and the subsets of a set of \(n\) elements, as follows. We already know by the definition of cardinality, that there is a bijection between any set of \(n\) elements, and the set \(\{1,\ldots, n\}\text{,}\) so we'll actually define a bijection between the subsets of \(\{1,\ldots, n\}\) and the binary strings of length \(n\text{.}\) Since the composition of two bijections is a bijection, this will indirectly define a bijection between our original set, and the binary strings of length \(n\text{.}\)

Given a subset of \(\{1,\ldots, n\}\text{,}\) the binary string that corresponds to this subset will be the binary string that has \(1\)s in the \(i\)th position if and only if \(i\) is in the subset. This tells us how to determine the binary string from the subset. We can also reverse (invert) the process. Given a binary string of length \(n\text{,}\) the corresponding subset of \(\{1, \ldots, n\}\) will be the subset whose elements are the positions of the \(1\)s in the binary string.

Although we haven't directly proven that this map from subsets to binary strings is both one-to-one and onto, an invertible function must be a bijection, so the fact that we were able to find an inverse function does prove that this map is a bijection. (You should check that you agree that the function we've claimed as an inverse really does invert the original function.)

Now, our imaginary table wouldn't be much use if we actually had to write it out. In order to write it out, we would need to know all of the subsets of our set already; and if we knew them all, we could certainly count them! Fortunately, we do not need to write it out. Instead, we use the bijection we have just defined. Rather than count the number of subsets of an \(n\)-set, we count the number of binary strings of length \(n\text{.}\) We can do this using just the multiplication rule! In each position there is either a zero or a one, so there are \(2\) choices for each of the \(n\) positions. Hence, there are \(2^n\) binary strings of length \(n\text{.}\)

We conclude that \(2^n\) subsets can be formed from a set of cardinality \(n\text{.}\)

Attacking this problem directly will get ugly. We would have to consider separately the cases of including one woman, two women, etc., all the way up to ten women, in our group, and add all of the resulting terms together. Instead, we note that there is an obvious bijection (the identity map) between groups that do include at least one woman, and groups that do not include exactly zero women. (We have previously seen this idea used intuitively in applications of the sum rule, for example when we worked out the number of ways of obtaining at least one \(1\) when rolling three six-sided dice, by actually working out the number of ways of not obtaining zero \(1\)s.)

The number of groups that do not include zero women is relatively easy to figure out: there are \(\binom{60}{10}\) possible groups of ten people that could be chosen from the \(60\) people. Of these, there are \(\binom{30}{10}\) groups that do include zero women (since the members of any such group must be chosen entirely from the \(30\) men). Therefore, the number of groups that do not include exactly zero women, is \(\binom{60}{10}-\binom{30}{10}\text{.}\)

Thanks to our bijection, we conclude that the number of groups that can be chosen, that will include at least one woman, is also \(\binom{60}{10}-\binom{30}{10}\text{.}\)