$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.1: Counting via Bijections

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

It can be hard to figure out how to count the number of outcomes for a particular problem. Sometimes it will be possible to find a different problem, and to prove that the two problems have the same number of outcomes (by finding a bijection between their outcomes). If we can work out how to count the outcomes for the second problem, then we’ve also solved the first problem! This may seem blatantly obvious intuitively, but this technique can provide simple solutions to problems that at first glance seem very difficult.

This technique of counting a set (or the number of outcomes to some problem) indirectly, via a different set or problem, is the bijective technique for counting. We begin with a classic example of this technique.

Example $$\PageIndex{1}$$

How many possible subsets are there, from a set of $$n$$ elements?

Solution

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\}$$:

 $$x$$ $$y$$ $$z$$ $$0$$ $$0$$ $$0$$ $$0$$ $$\{x\}$$ $$1$$ $$0$$ $$0$$ $$\{y\}$$ $$0$$ $$1$$ $$0$$ $$\{z\}$$ $$0$$ $$0$$ $$1$$ $$\{x,y\}$$ $$1$$ $$1$$ $$0$$ $$\{x,z\}$$ $$1$$ $$0$$ $$1$$ $$\{y,z\}$$ $$0$$ $$1$$ $$1$$ $$\{x,y,z\}$$ $$1$$ $$1$$ $$1$$

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$$, 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$$, 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 our set of $$n$$ elements, and the set $$\{1, . . . , n\}$$, so we’ll actually define a bijection between the subsets of $$\{1, . . . , n\}$$ and the binary strings of length $$n$$. 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$$.

Given a subset of $$\{1, . . . , n\}$$, 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$$, the corresponding subset of $$\{1, . . . , 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$$. 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$$.

We conclude that $$2^n$$ subsets can be formed from a set of cardinality $$n$$.

In some ways, we’ve actually been using this idea pretty much every time we’ve come up with more than one way to solve a problem. Implicitly, finding a different way of thinking of the problem is equivalent to finding a bijection between the solutions to these different approaches.

Example $$\PageIndex{2}$$

How many ways are there to choose ten people from a group of $$30$$ men and $$30$$ women, if the group must include at least one woman?

Solution

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.

The latter 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 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}$$.

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}$$.

Exercise $$\PageIndex{1}$$

The following problems should help you in working with the bijective technique for counting.

1. We define a structure that is like a subset, except that any element of the original set may appear $$0$$, $$1$$, or $$2$$ times in the structure. How many of these structures can we form from the set $$\{1, . . . , n\}$$?
2. Find a bijection between the coefficient of $$x^r$$ in $$(1 + x)^n$$, and the number of $$r$$-combinations of an $$n$$-set.
3. Find a bijection between the number of ways in which three different dolls can be put into ten numbered cribs, and the number of ways in which ten Olympic contenders can win the medals in their event.