1.6 Advanced Counting Using PIE 容斥原理高级计数

本页译自 LibreTexts · Discrete Mathematics (Levin) 第 1.6 章。公式经 MathJax 渲染，自定义宏已注入。

Investigate! 探究！

You have 11 identical mini key-lime pies to give to 4 children. However, you don't want any kid to get more than 3 pies. How many ways can you distribute the pies?

1. How many ways are there to distribute the pies without any restriction?
2. Let's get rid of the ways that one or more kid gets too many pies. How many ways are there to distribute the pies if Al gets too many pies? What if Bruce gets too many? Or Cat? Or Dent?
3. What if two kids get too many pies? How many ways can this happen? Does it matter which two kids you pick to overfeed?
4. Is it possible that three kids get too many pies? If so, how many ways can this happen?
5. How should you combine all the numbers you found above to answer the original question?

1. 不加任何限制时，共有多少种分法？
2. 我们要剔除「一个或多个孩子拿到过多派」的分法。若 Al 拿到过多派，共有多少种分法？若 Bruce 过多呢？Cat 呢？还是 Dent？
3. 若两个孩子都拿到过多派呢？共有多少种这样的分法？具体选哪两个孩子喂过量，是否影响结果？
4. 是否可能三个孩子都拿到过多派？如果可能，共有多少种分法？
5. 应如何把上面算出的所有数字组合起来，以回答原问题？

Suppose now you have 13 pies and 7 children. No child can have more than 2 pies. How many ways can you distribute the pies?

Stars and bars allows us to count the number of ways to distribute 10 cookies to 3 kids and natural number solutions to \(x+y+z = 11\text{,}\) for example. A relatively easy modification allows us to put a lower bound restriction on these problems: perhaps each kid must get at least two cookies or \(x,y,z \ge 2\text{.}\) This was done by first assigning each kid (or variable) 2 cookies (or units) and then distributing the rest using stars and bars.

What if we wanted an upper bound restriction? For example, we might insist that no kid gets more than 4 cookies or that \(x, y, z \le 4\text{.}\) It turns out this is considerably harder, but still possible. The idea is to count all the distributions and then remove those that violate the condition. In other words, we must count the number of ways to distribute 11 cookies to 3 kids in which one or more of the kids gets more than 4 cookies. For any particular kid, this is not a problem; we do this using stars and bars. But how to combine the number of ways for kid A, or B or C? We must use the PIE.

The Principle of Inclusion/Exclusion (PIE) gives a method for finding the cardinality of the union of not necessarily disjoint sets. We saw in Subsection how this works with three sets. To find how many things are in one or more of the sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\) we should just add up the number of things in each of these sets. However, if there is any overlap among the sets, those elements are counted multiple times. So we subtract the things in each intersection of a pair of sets. But doing this removes elements which are in all three sets once too often, so we need to add it back in. In terms of cardinality of sets, we have

\begin{equation*} \|A \cup B \cup C\| = \|A\| + \|B\| + \|C\| - \|A \cap B\| - \|A \cap C\| - \|B \cap C\| + \|A\cap B \cap C\|. \end{equation*}

Example 1

Three kids, Alberto, Bernadette, and Carlos, decide to share 11 cookies. They wonder how many ways they could split the cookies up provided that none of them receive more than 4 cookies (someone receiving no cookies is for some reason acceptable to these kids).

Solution

Without the “no more than 4” restriction, the answer would be \({13 \choose 2}\text{,}\) using 11 stars and 2 bars (separating the three kids). Now count the number of ways that one or more of the kids violates the condition, i.e., gets at least 4 cookies.

Let \(A\) be the set of outcomes in which Alberto gets more than 4 cookies. Let \(B\) be the set of outcomes in which Bernadette gets more than 4 cookies. Let \(C\) be the set of outcomes in which Carlos gets more than 4 cookies. We then are looking (for the sake of subtraction) for the size of the set \(A \cup B \cup C\text{.}\) Using PIE, we must find the sizes of \(\|A\|\text{,}\) \(\|B\|\text{,}\) \(\|C\|\text{,}\) \(\|A\cap B\|\) and so on. Here is what we find.

• \(\|A\| = {8 \choose 2}\text{.}\) First give Alberto 5 cookies, then distribute the remaining 6 to the three kids without restrictions, using 6 stars and 2 bars.
• \(\|B\| = {8 \choose 2}\text{.}\) Just like above, only now Bernadette gets 5 cookies at the start.
• \(\|C\| = {8 \choose 2}\text{.}\) Carlos gets 5 cookies first.
• \(\|A \cap B\| = {3 \choose 2}\text{.}\) Give Alberto and Bernadette 5 cookies each, leaving 1 (star) to distribute to the three kids (2 bars).
• \(\|A \cap C\| = {3 \choose 2}\text{.}\) Alberto and Carlos get 5 cookies first.
• \(\|B \cap C\| = {3 \choose 2}\text{.}\) Bernadette and Carlos get 5 cookies first.
• \(\|A \cap B \cap C\| = 0\text{.}\) It is not possible for all three kids to get 4 or more cookies.

• \(\|A\| = {8 \choose 2}\text{。}\) 先给 Alberto 5 块饼干，再把剩下的 6 块无限制地分给三个孩子，用 6 颗星和 2 根竖线。
• \(\|B\| = {8 \choose 2}\text{。}\) 同上，只是先给 Bernadette 5 块饼干。
• \(\|C\| = {8 \choose 2}\text{。}\) 先给 Carlos 5 块饼干。
• \(\|A \cap B\| = {3 \choose 2}\text{。}\) 给 Alberto 和 Bernadette 各 5 块饼干，剩下 1 块（1 颗星）分给三个孩子（2 根竖线）。
• \(\|A \cap C\| = {3 \choose 2}\text{。}\) 先给 Alberto 和 Carlos 各 5 块饼干。
• \(\|B \cap C\| = {3 \choose 2}\text{。}\) 先给 Bernadette 和 Carlos 各 5 块饼干。
• \(\|A \cap B \cap C\| = 0\text{。}\) 三个孩子同时拿到 4 块或更多饼干是不可能的。

Combining all of these we see

\begin{equation*} \|A \cup B \cup C\| = {8 \choose 2} + {8 \choose 2} + {8 \choose 2} - {3 \choose 2} - {3 \choose 2} - {3 \choose 2} + 0 = 75. \end{equation*}

Thus the answer to the original question is \({13 \choose 2} - 75 = 78 - 75 = 3\text{.}\) This makes sense now that we see it. The only way to ensure that no kid gets more than 4 cookies is to give two kids 4 cookies and one kid 3; there are three choices for which kid that should be. We could have found the answer much quicker through this observation, but the point of the example is to illustrate that PIE works!

For four or more sets, we do not write down a formula for PIE. Instead, we just think of the principle: add up all the elements in single sets, then subtract out things you counted twice (elements in the intersection of a pair of sets), then add back in elements you removed too often (elements in the intersection of groups of three sets), then take back out elements you added back in too often (elements in the intersection of groups of four sets), then add back in, take back out, add back in, etc. This would be very difficult if it wasn't for the fact that in these problems, all the cardinalities of the single sets are equal, as are all the cardinalities of the intersections of two sets, and that of three sets, and so on. Thus we can group all of these together and multiply by how many different combinations of 1, 2, 3, … sets there are.

Example 2

How many ways can you distribute 10 cookies to 4 kids so that no kid gets more than 2 cookies?

Solution

There are \({13 \choose 3}\) ways to distribute 10 cookies to 4 kids (using 10 stars and 3 bars). We will subtract all the outcomes in which a kid gets 3 or more cookies. How many outcomes are there like that? We can force kid A to eat 3 or more cookies by giving him 3 cookies before we start. Doing so reduces the problem to one in which we have 7 cookies to give to 4 kids without any restrictions. In that case, we have 7 stars (the 7 remaining cookies) and 3 bars (one less than the number of kids) so we can distribute the cookies in \({10 \choose 3}\) ways. Of course we could choose any one of the 4 kids to give too many cookies, so it would appear that there are \({4 \choose 1}{10 \choose 3}\) ways to distribute the cookies giving too many to one kid. But in fact, we have over counted.

We must get rid of the outcomes in which two kids have too many cookies. There are \({4 \choose 2}\) ways to select 2 kids to give extra cookies. It takes 6 cookies to do this, leaving only 4 cookies. So we have 4 stars and still 3 bars. The remaining 4 cookies can thus be distributed in \({7 \choose 3}\) ways (for each of the \({4 \choose 2}\) choices of which 2 kids to over-feed).

But now we have removed too much. We must add back in all the ways to give too many cookies to three kids. This uses 9 cookies, leaving only 1 to distribute to the 4 kids using stars and bars, which can be done in \({4 \choose 3}\) ways. We must consider this outcome for every possible choice of which three kids we over-feed, and there are \({4 \choose 3}\) ways of selecting that set of 3 kids.

Next we would subtract all the ways to give four kids too many cookies, but in this case, that number is 0.

All together we get that the number of ways to distribute 10 cookies to 4 kids without giving any kid more than 2 cookies is:

\begin{equation*} {13 \choose 3} - \left( {4 \choose 1}{10 \choose 3} - {4 \choose 2}{7 \choose 3} + {4\choose 3}{4\choose 3} \right) \end{equation*}

which is

\begin{equation*} 286 - (480 - 210 + 16) = 0. \end{equation*}

This makes sense: there is NO way to distribute 10 cookies to 4 kids and make sure that nobody gets more than 2. It is slightly surprising that

\begin{equation*} {13 \choose 3} = \left( {4 \choose 1}{10 \choose 3} - {4 \choose 2}{7 \choose 3} + {4\choose 3}{4\choose 3} \right) \end{equation*}

but since PIE works, this equality must hold.

Just so you don't think that these problems always have easier solutions, consider the following example.

Example 3

Earlier (Example 1.5.3) we counted the number of solutions to the equation

\begin{equation*} x_1 + x_2 + x_3 + x_4 + x_5 = 13 \end{equation*}

where \(x_i \ge 0\) for each \(x_i\text{.}\)

How many of those solutions have \(0 \le x_i \le 3\) for each \(x_i\text{?}\)

Solution

We must subtract off the number of solutions in which one or more of the variables has a value greater than 3. We will need to use PIE because counting the number of solutions for which each of the five variables separately are greater than 3 counts solutions multiple times. Here is what we get:

• Total solutions: \({17 \choose 4}\text{.}\)
• Solutions where \(x_1 > 3\text{:}\) \({13 \choose 4}\text{.}\) Give \(x_1\) 4 units first, then distribute the remaining 9 units to the 5 variables.
• Solutions where \(x_1 > 3\) and \(x_2 > 3\text{:}\) \({9 \choose 4}\text{.}\) After you give 4 units to \(x_1\) and another 4 to \(x_2\text{,}\) you only have 5 units left to distribute.
• Solutions where \(x_1 > 3\text{,}\) \(x_2 > 3\) and \(x_3 > 3\text{:}\) \({5 \choose 4}\text{.}\)
• Solutions where \(x_1 > 3\text{,}\) \(x_2 > 3\text{,}\) \(x_3 > 3\text{,}\) and \(x_4 > 3\text{:}\) 0.

• 解的总数：\({17 \choose 4}\text{。}\)
• \(x_1 > 3\) 的解：\({13 \choose 4}\text{。}\) 先给 \(x_1\) 4 个单位，再把剩下的 9 个单位分给 5 个变量。
• \(x_1 > 3\) 且 \(x_2 > 3\) 的解：\({9 \choose 4}\text{。}\) 给 \(x_1\) 4 个单位、再给 \(x_2\) 4 个单位后，只剩 5 个单位可分。
• \(x_1 > 3\text{、}\) \(x_2 > 3\) 且 \(x_3 > 3\) 的解：\({5 \choose 4}\text{。}\)
• \(x_1 > 3\text{、}\) \(x_2 > 3\text{、}\) \(x_3 > 3\text{、}\) \(x_4 > 3\) 的解：0。

We also need to account for the fact that we could choose any of the five variables in the place of \(x_1\) above (so there will be \({5 \choose 1}\) outcomes like this), any pair of variables in the place of \(x_1\) and \(x_2\) (\({5 \choose 2}\) outcomes) and so on. It is because of this that the double counting occurs, so we need to use PIE. All together we have that the number of solutions with \(0 \le x_i \le 3\) is

\begin{equation*} {17 \choose 4} - \left( {5\choose 1}{13 \choose 4} - {5 \choose 2}{9 \choose 4} + {5 \choose 3}{5 \choose 4} \right) = 15. \end{equation*}

Counting Derangements 错位排列计数

Investigate! 探究！

For your senior prank, you decide to switch the nameplates on your favorite 5 professors' doors. So that none of them feel left out, you want to make sure that all of the nameplates end up on the wrong door. How many ways can this be accomplished?

The advanced use of PIE has applications beyond stars and bars. A derangement of \(n\) elements \(1,2,3,\ldots,n\) is a permutation in which no element is fixed. For example, there are \(6\) permutations of the three elements \(1,2,3\text{:}\)

\begin{equation*} 123 \sim 132 \sim 213 \sim 231 \sim 312 \sim 321. \end{equation*}

but most of these have one or more elements fixed: \(123\) has all three elements fixed since all three elements are in their original positions, \(132\) has the first element fixed (1 is in its original first position), and so on. In fact, the only derangements of three elements are

\begin{equation*} 231 \text{ and } 312. \end{equation*}

If we go up to 4 elements, there are 24 permutations (because we have 4 choices for the first element, 3 choices for the second, 2 choices for the third leaving only 1 choice for the last). How many of these are derangements? If you list out all 24 permutations and eliminate those which are not derangements, you will be left with just 9 derangements. Let's see how we can get that number using PIE.

Example 4

How many derangements are there of 4 elements?

Solution

We count all permutations, and subtract those which are not derangements. There are \(4! = 24\) permutations of 4 elements. Now for a permutation to not be a derangement, at least one of the 4 elements must be fixed. There are \({4 \choose 1}\) choices for which single element we fix. Once fixed, we need to find a permutation of the other three elements. There are \(3!\) permutations on 3 elements. But now we have counted too many non-derangements, so we must subtract those permutations which fix two elements. There are \({4 \choose 2}\) choices for which two elements we fix, and then for each pair, \(2!\) permutations of the remaining elements. But this subtracts too many, so add back in permutations which fix 3 elements, all \({4 \choose 3}1!\) of them. Finally subtract the \({4 \choose 4}0!\) permutations (recall \(0! = 1\) which fix all four elements. All together we get that the number of derangements of 4 elements is:

\begin{equation*} 4! - \left( {4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4}0! \right) = 24 - 15 = 9. \end{equation*}

Of course we can use a similar formula to count the derangements of any number of elements. However, the more elements we have, the longer the formula gets. Here is another example:

Example 5

Five gentlemen attend a party, leaving their hats at the door. At the end of the party, they hastily grab hats on their way out. How many different ways could this happen so that none of the gentlemen leave with their own hat?

Solution

We are counting derangements on 5 elements. There are \(5!\) ways for the gentlemen to grab hats in any order—but many of these permutations will result in someone getting their own hat. So we subtract all the ways in which one or more of the men get their own hat. In other words, we subtract the non-derangements. Doing so requires PIE. Thus the answer is:

\begin{equation*} 5! - \left( {5 \choose 1}4! - {5 \choose 2}3! + {5 \choose 3}2! - {5 \choose 4}1! + {5\choose 5}0! \right). \end{equation*}

Counting Functions 函数计数

Investigate! 探究！

• Consider all functions \(f: 1,2,3,4,5 \to 1,2,3,4,5\text{.}\) How many functions are there all together? How many of those are injective? Remember, a function is an injection if every input goes to a different output.
• Consider all functions \(f: 1,2,3,4,5 \to 1,2,3,4,5\text{.}\) How many of the injections have the property that \(f(x) \ne x\) for any \(x \in 1,2,3,4,5\)? Your friend claims that the answer is:

  \begin{equation*} 5! - \left( {5\choose 1}4! - {5 \choose 2}3! + {5\choose 3}2! - {5 \choose 4}1! + {5\choose 5}0! \right). \end{equation*}

  Explain why this is correct.
• Recall that a surjection is a function for which every element of the codomain is in the range. How many of the functions \(f: 1,2,3,4,5 \to 1,2,3,4,5\) are surjective? Use PIE!

• 考虑所有函数 \(f: 1,2,3,4,5 \to 1,2,3,4,5\text{。}\) 总共有多少个函数？其中有多少个是单射？记住：若每个输入都对应不同的输出，该函数就是单射。
• 考虑所有函数 \(f: 1,2,3,4,5 \to 1,2,3,4,5\text{。}\) 其中有多少个单射满足：对任意 \(x \in 1,2,3,4,5\) 都有 \(f(x) \ne x\)？你的朋友断言答案是：

  \begin{equation*} 5! - \left( {5\choose 1}4! - {5 \choose 2}3! + {5\choose 3}2! - {5 \choose 4}1! + {5\choose 5}0! \right). \end{equation*}

  请解释为什么这是正确的。
• 回顾：满射是指上域中每个元素都在值域里的函数。在函数 \(f: 1,2,3,4,5 \to 1,2,3,4,5\) 中，有多少个是满射？用容斥原理！

We have seen throughout this chapter that many counting questions can be rephrased as questions about counting functions with certain properties. This is reasonable since many counting questions can be thought of as counting the number of ways to assign elements from one set to elements of another.

Example 6

You decide to give away your video game collection so to better spend your time studying advance mathematics. How many ways can you do this, provided:

1. You want to distribute your 3 different PS4 games among 5 friends, so that no friend gets more than one game?
2. You want to distribute your 8 different 3DS games among 5 friends?
3. You want to distribute your 8 different SNES games among 5 friends, so that each friend gets at least one game?

1. 把 3 款不同的 PS4 游戏分给 5 个朋友，每位朋友最多拿一款？
2. 把 8 款不同的 3DS 游戏分给 5 个朋友？
3. 把 8 款不同的 SNES 游戏分给 5 个朋友，要求每位朋友至少拿到一款？

In each case, model the counting question as a function counting question.

Solution

We must use the three games (call them 1, 2, 3) as the domain and the 5 friends (a,b,c,d,e) as the codomain (otherwise the function would not be defined for the whole domain when a friend didn't get any game). So how many functions are there with domain \(1,2,3\) and codomain \(a,b,c,d,e\text{?}\) The answer to this is \(5^3=125\text{,}\) since we can assign any of 5 elements to be the image of 1, any of 5 elements to be the image of 2 and any of 5 elements to be the image of 3.

But this is not the correct answer to our counting problem, because one of these functions is \(f= \begin{pmatrix}1 & 2 & 3 \\ a & a & a\end{pmatrix}\text{;}\) one friend can get more than one game. What we really need to do is count injective functions. This gives \(P(5,3) = 60\) functions, which is the answer to our counting question.

Again, we need to use the 8 games as the domain and the 5 friends as the codomain. We are counting all functions, so the number of ways to distribute the games is \(5^8\text{.}\)

This question is harder. Use the games as the domain and friends as the codomain (otherwise an element of the domain would have more than one image, which is impossible). To ensure that every friend gets at least one game means that every element of the codomain is in the range. In other words, we are looking for surjective functions. How do you count those?

In Example 1.1.5 we saw how to count all functions (using the multiplicative principle) and in Example 1.3.4 we learned how to count injective functions (using permutations). Surjective functions are not as easily counted (unless the size of the domain is smaller than the codomain, in which case there are none).

The idea is to count the functions which are not surjective, and then subtract that from the total number of functions. This works very well when the codomain has two elements in it:

Example 7

How many functions \(f: 1,2,3,4,5 \to a,b\) are surjective?

Solution

There are \(2^5\) functions all together, two choices for where to send each of the 5 elements of the domain. Now of these, the functions which are not surjective must exclude one or more elements of the codomain from the range. So first, consider functions for which \(a\) is not in the range. This can only happen one way: everything gets sent to \(b\text{.}\) Alternatively, we could exclude \(b\) from the range. Then everything gets sent to \(a\text{,}\) so there is only one function like this. These are the only ways in which a function could not be surjective (no function excludes both \(a\) and \(b\) from the range) so there are exactly \(2^5 - 2\) surjective functions.

When there are three elements in the codomain, there are now three choices for a single element to exclude from the range. Additionally, we could pick pairs of two elements to exclude from the range, and we must make sure we don't over count these. It's PIE time!

Example 8

How many functions \(f: 1,2,3,4,5 \to a,b,c\) are surjective?

Solution

Again start with the total number of functions: \(3^5\) (as each of the five elements of the domain can go to any of three elements of the codomain). Now we count the functions which are not surjective.

Start by excluding \(a\) from the range. Then we have two choices (\(b\) or \(c\) for where to send each of the five elements of the domain. Thus there are \(2^5\) functions which exclude \(a\) from the range. Similarly, there are \(2^5\) functions which exclude \(b\text{,}\) and another \(2^5\) which exclude \(c\text{.}\) Now have we counted all functions which are not surjective? Yes, but in fact, we have counted some multiple times. For example, the function which sends everything to \(c\) was one of the \(2^5\) functions we counted when we excluded \(a\) from the range, and also one of the \(2^5\) functions we counted when we excluded \(b\) from the range. We must subtract out all the functions which specifically exclude two elements from the range. There is 1 function when we exclude \(a\) and \(b\) (everything goes to \(c\)), one function when we exclude \(a\) and \(c\text{,}\) and one function when we exclude \(b\) and \(c\text{.}\)

We are using PIE: to count the functions which are not surjective, we added up the functions which exclude \(a\text{,}\) \(b\text{,}\) and \(c\) separately, then subtracted the functions which exclude pairs of elements. We would then add back in the functions which exclude groups of three elements, except that there are no such functions. We find that the number of functions which are not surjective is

\begin{equation*} 2^5 + 2^5 + 2^5 - 1 - 1 - 1 + 0. \end{equation*}

Perhaps a more descriptive way to write this is

\begin{equation*} {3 \choose 1}2^5 - {3 \choose 2}1^5 + {3 \choose 3}0^5. \end{equation*}

since each of the \(2^5\)'s was the result of choosing 1 of the 3 elements of the codomain to exclude from the range, each of the three \(1^5\)'s was the result of choosing 2 of the 3 elements of the codomain to exclude. Writing \(1^5\) instead of 1 makes sense too: we have 1 choice of were to send each of the 5 elements of the domain.

Now we can finally count the number of surjective functions:

\begin{equation*} 3^5 - \left( {3 \choose 1}2^5 - {3 \choose 2}1^5 \right) = 150. \end{equation*}

You might worry that to count surjective functions when the codomain is larger than 3 elements would be too tedious. We need to use PIE but with more than 3 sets the formula for PIE is very long. However, we have lucked out. As we saw in the example above, the number of functions which exclude a single element from the range is the same no matter which single element is excluded. Similarly, the number of functions which exclude a pair of elements will be the same for every pair. With larger codomains, we will see the same behavior with groups of 3, 4, and more elements excluded. So instead of adding/subtracting each of these, we can simply add or subtract all of them at once, if you know how many there are. This works just like it did in for the other types of counting questions in this section, only now the size of the various combinations of sets is a number raised to a power, as opposed to a binomial coefficient or factorial. Here's what happens with \(4\) and \(5\) elements in the codomain.

Example 9

1. How many functions \(f: 1,2,3,4,5 \to a,b,c,d\) are surjective?
2. How many functions \(f: 1,2,3,4,5 \to a,b,c,d,e\) are surjective?

1. 有多少个函数 \(f: 1,2,3,4,5 \to a,b,c,d\) 是满射？
2. 有多少个函数 \(f: 1,2,3,4,5 \to a,b,c,d,e\) 是满射？

Solution

There are \(4^5\) functions all together; we will subtract the functions which are not surjective. We could exclude any one of the four elements of the codomain, and doing so will leave us with \(3^5\) functions for each excluded element. This counts too many so we subtract the functions which exclude two of the four elements of the codomain, each pair giving \(2^5\) functions. But this excludes too many, so we add back in the functions which exclude three of the four elements of the codomain, each triple giving \(1^5\) function. There are \({4 \choose 1}\) groups of functions excluding a single element, \({4 \choose 2}\) groups of functions excluding a pair of elements, and \({4 \choose 3}\) groups of functions excluding a triple of elements. This means that the number of functions which are not surjective is:

\begin{equation*} {4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5. \end{equation*}

We can now say that the number of functions which are surjective is:

\begin{equation*} 4^5 - \left( {4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5 \right). \end{equation*}

The number of surjective functions is:

\begin{equation*} 5^5 - \left( {5 \choose 1}4^5 - {5 \choose 2}3^5 + {5 \choose 3}2^5 - {5 \choose 4}1^5 \right). \end{equation*}

We took the total number of functions \(5^5\) and subtracted all that were not surjective. There were \({5 \choose 1}\) ways to select a single element from the codomain to exclude from the range, and for each there were \(4^5\) functions. But this double counts, so we use PIE and subtract functions excluding two elements from the range: there are \({5 \choose 2}\) choices for the two elements to exclude, and for each pair, \(3^5\) functions. This takes out too many functions, so we add back in functions which exclude 3 elements from the range: \({5 \choose 3}\) choices for which three to exclude, and then \(2^5\) functions for each choice of elements. Finally we take back out the 1 function which excludes 4 elements for each of the \({5 \choose 4}\) choices of 4 elements.

If you happen to calculate this number precisely, you will get 120 surjections. That happens to also be the value of \(5!\text{.}\) This might seem like an amazing coincidence until you realize that every surjective function \(f:X \to Y\) with \(\left\|X\right\| = \left\|Y\right\|\) finite must necessarily be a bijection. The number of bijections is always \(\left\|X\right\|!\) in this case. What we have here is a combinatorial proof of the following identity:

\begin{equation*} n^n - \left( {n\choose 1}(n-1)^n - {n \choose 2}(n-2)^n + \cdots + {n \choose n-1}1^n \right) = n!. \end{equation*}

We have seen that counting surjective functions is another nice example of the advanced use of the Principle of Inclusion/Exclusion. Also, counting injective functions turns out to be equivalent to permutations, and counting all functions has a solution akin to those counting problems where order matters but repeats are allowed (like counting the number of words you can make from a given set of letters).

These are not just a few more examples of the techniques we have developed in this chapter. Quite the opposite: everything we have learned in this chapter are examples of counting functions!

Example 10

How many 5-letter words can you make using the eight letters \(a\) through \(h\text{?}\) How many contain no repeated letters?

Solution

By now it should be no surprise that there are \(8^5\) words, and \(P(8,5)\) words without repeated letters. The new piece here is that we are actually counting functions. For the first problem, we are counting all functions from \(1,2,\ldots, 5\) to \(a,b,\ldots, h\text{.}\) The numbers in the domain represent the position of the letter in the word, the codomain represents the letter that could be assigned to that position. If we ask for no repeated letters, we are asking for injective functions.

If \(A\) and \(B\) are any sets with \(\|A\| = 5\) and \(\|B\| = 8\text{,}\) then the number of functions \(f: A \to B\) is \(8^5\) and the number of injections is \(P(8,5)\text{.}\) So if you can represent your counting problem as a function counting problem, most of the work is done.

Example 11

How many subsets are there of \(1,2,\ldots, 9\text{?}\) How many 9-bit strings are there (of any weight)?

Solution

We saw in Section 1.2 that the answer to both these questions is \(2^9\text{,}\) as we can say yes or no (or 0 or 1) to each of the 9 elements in the set (positions in the bit-string). But \(2^9\) also looks like the answer you get from counting functions. In fact, if you count all functions \(f: A \to B\) with \(\|A\| = 9\) and \(\|B\| = 2\text{,}\) this is exactly what you get.

This makes sense! Let \(A = 1,2,\ldots, 9\) and \(B = y, n\text{.}\) We are assigning each element of the set either a yes or a no. Or in the language of bit-strings, we would take the 9 positions in the bit string as our domain and the set \(0,1\) as the codomain.

So far we have not used a function as a model for binomial coefficients (combinations). Think for a moment about the relationship between combinations and permutations, say specifically \({9 \choose 3}\) and \(P(9,3)\text{.}\) We do have a function model for \(P(9,3)\text{.}\) This is the number of injective functions from a set of size 3 (say \(1,2,3\) to a set of size 9 (say \(1,2,\ldots, 9\) since there are 9 choices for where to send the first element of the domain, then only 8 choices for the second, and 7 choices for the third. For example, the function might look like this:

\begin{equation*} f(1) = 5 \qquad f(2) = 8 \qquad f(3) = 4. \end{equation*}

This is a different function from:

\begin{equation*} f(1) = 4 \qquad f(2) = 5 \qquad f(3) = 8. \end{equation*}

Now \(P(9,3)\) counts these as different outcomes correctly, but \({9\choose 3}\) will count these (among others) as just one outcome. In fact, in terms of functions \({9 \choose 3}\) just counts the number of different ranges possible of injective functions. This should not be a surprise since binomial coefficients counts subsets, and the range is a possible subset of the codomain. ⁴ A more mathematically sophisticated interpretation of combinations is that we are defining two injective functions to be equivalent if they have the same range, and then counting the number of equivalence classes under this notion of equivalence.

While it is possible to interpret combinations as functions, perhaps the better advice is to instead use combinations (or stars and bars) when functions are not quite the right way to interpret the counting question.