2.6 Advanced Counting Using PIE

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?

How many ways are there to distribute the pies without any restriction?
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?
What if two kids get too many pies? How many ways can this happen? Does it matter which two kids you pick to overfeed?
Is it possible that three kids get too many pies? If so, how many ways can this happen?
How should you combine all the numbers you found above to answer the original question?

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$ , 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 greater than or equal to 2$ . 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 less than or equal to 4$ . 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 Additive and Multiplicative Principles how this works with three sets. To find how many things are in one or more of the sets $A$ , $B$ , and $C$ , 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

$| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |$

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).

Without the “no more than 4” restriction, the answer would be $(\binom{13}{2})$ , 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$ . Using PIE, we must find the sizes of $| A |$ , $| B |$ , $| C |$ , $| A \cap B |$ and so on. Here is what we find.

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

Combining all of these we see

$| A \cup B \cup C | = (\binom{8}{2}) + (\binom{8}{2}) + (\binom{8}{2}) - (\binom{3}{2}) - (\binom{3}{2}) - (\binom{3}{2}) + 0 = 75$

Thus the answer to the original question is $(\binom{13}{2}) - 75 = 78 - 75 = 3$ . 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?

There are $(\binom{13}{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 $(\binom{10}{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 $(\binom{4}{1}) (\binom{10}{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 $(\binom{4}{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 $(\binom{7}{3})$ ways (for each of the $(\binom{4}{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 $(\binom{4}{3})$ ways. We must consider this outcome for every possible choice of which three kids we over-feed, and there are $(\binom{4}{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:

$(\binom{13}{3}) - [(\binom{4}{1}) (\binom{10}{3}) - (\binom{4}{2}) (\binom{7}{3}) + (\binom{4}{3}) (\binom{4}{3})]$

which is

$286 - [480 - 210 + 16] = 0$

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

$(\binom{13}{3}) = [(\binom{4}{1}) (\binom{10}{3}) - (\binom{4}{2}) (\binom{7}{3}) + (\binom{4}{3}) (\binom{4}{3})]$

, 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) we counted the number of solutions to the equation

$x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 13$

, where $x sub i greater than or equal to 0$ for each $x_{i}$ .

How many of those solutions have $0 less than or equal to x sub i less than or equal to 3$ for each $x_{i}$ ?

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: $(\binom{17}{4})$ .
Solutions where $x sub 1 greater than 3$ : $(\binom{13}{4})$ . Give $x sub 1$ 4 units first, then distribute the remaining 9 units to the 5 variables.
Solutions where $x sub 1 greater than 3$ and $x sub 2 greater than 3$ : $(\binom{9}{4})$ . After you give 4 units to $x sub 1$ and another 4 to $x sub 2$ , you only have 5 units left to distribute.
Solutions where $x sub 1 greater than 3$ , $x sub 2 greater than 3$ and $x sub 3 greater than 3$ : $(\binom{5}{4})$ .
Solutions where $x sub 1 greater than 3$ , $x sub 2 greater than 3$ , $x sub 3 greater than 3$ , and $x sub 4 greater than 3$ : 0.

We also need to account for the fact that we could choose any of the five variables in the place of $x sub 1$ above (so there will be $(\binom{5}{1})$ outcomes like this), any pair of variables in the place of $x sub 1$ and $x sub 2$ ( $(\binom{5}{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 less than or equal to x sub i less than or equal to 3$ is

$(\binom{17}{4}) - [(\binom{5}{1}) (\binom{13}{4}) - (\binom{5}{2}) (\binom{9}{4}) + (\binom{5}{3}) (\binom{5}{4})] = 15$

Counting Derangements

The advanced use of PIE has applications beyond stars and bars. A derangement of $n$ elements $open brace 1, 2, 3, and so on, n close brace$ is a permutation in which no element is fixed. For example, there are $6$ permutations of the three elements $open brace 1, 2, 3 close brace$ :

$123132213231312321$

. 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

$231 and 312$

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?

We count all permutations, and subtract those which are not derangements. There are $4 ! equals 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 $(\binom{4}{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 $(\binom{4}{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 $(\binom{4}{3}) 1!$ of them. Finally subtract the $(\binom{4}{4}) 0!$ permutations (recall $0 ! equals 1$ ) which fix all four elements. All together we get that the number of derangements of 4 elements is:

$4! - [(\binom{4}{1}) 3! - (\binom{4}{2}) 2! + (\binom{4}{3}) 1! - (\binom{4}{4}) 0!] = 24 - 15 = 9$

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 his own hat?

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:

$5! - [(\binom{5}{1}) 4! - (\binom{5}{2}) 3! + (\binom{5}{3}) 2! - (\binom{5}{4}) 1! + (\binom{5}{5}) 0!]$

Counting Functions

Investigate!

Consider all functions $f: open brace 1, 2, 3, 4, 5 close brace → open brace 1, 2, 3, 4, 5 close brace$ . 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: open brace 1, 2, 3, 4, 5 close brace → open brace 1, 2, 3, 4, 5 close brace$ . How many of the injections have the property that $f (x) \neq x$ for any $x ∈ open brace 1, 2, 3, 4, 5 close brace$ ?
Your friend claims that the answer is:
$5! - [(\binom{5}{1}) 4! - (\binom{5}{2}) 3! + (\binom{5}{3}) 2! - (\binom{5}{4}) 1! + (\binom{5}{5}) 0!]$
.
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: open brace 1, 2, 3, 4, 5 close brace → open brace 1, 2, 3, 4, 5 close brace$ are surjective? Use PIE!

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 as to better spend your time studying advanced mathematics. How many ways can you do this, provided:

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

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

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 $open brace 1, 2, 3 close brace$ and codomain ${a, b, c, d, e}$ ? The answer to this is $5 cubed equals 125$ , 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 equals open parenthesis 1, 2, 3; a, a, a close parenthesis$ ; one friend can get more than one game. What we really need to do is count injective functions. This gives $P open parenthesis 5, 3 close parenthesis equals 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 to the power 8$ .
This question is harder. Use the games as the domain and friends as the codomain (the reverse would not give a function). 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 Counting functions we saw how to count all functions (using the multiplicative principle) and in Counting injective functions 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: open brace 1, 2, 3, 4, 5 close brace → open brace a, b close brace$ are surjective?

There are $2 to the power 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$ . Alternatively, we could exclude $b$ from the range. Then everything gets sent to $a$ , 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: open brace 1, 2, 3, 4, 5 close brace → open brace a, b, c close brace$ are surjective?

Again start with the total number of functions: $3 to the power 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 to the power 5$ functions which exclude $a$ from the range. Similarly, there are $2 to the power 5$ functions which exclude $b$ , and another $2 to the power 5$ which exclude $c$ . 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 to the power 5$ functions we counted when we excluded $a$ from the range, and also one of the $2 to the power 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$ , and one function when we exclude $b$ and $c$ .

We are using PIE: to count the functions which are not surjective, we added up the functions which exclude $a$ , $b$ , 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

$2^{5} + 2^{5} + 2^{5} - 1 - 1 - 1 + 0$

Perhaps a more descriptive way to write this is

$(\binom{3}{1}) 2^{5} - (\binom{3}{2}) 1^{5} + (\binom{3}{3}) 0^{5}$

. since each of the $2 to the power 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 to the power 5$ 's was the result of choosing 2 of the 3 elements of the codomain to exclude. Writing $1 to the power 5$ instead of 1 makes sense too: we have 1 choice of where to send each of the 5 elements of the domain.

Now we can finally count the number of surjective functions:

$3^{5} - [(\binom{3}{1}) 2^{5} - (\binom{3}{2}) 1^{5}] = 150$

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

How many functions $f: open brace 1, 2, 3, 4, 5 close brace → open brace a, b, c, d close brace$ are surjective?
How many functions $f: open brace 1, 2, 3, 4, 5 close brace → open brace a, b, c, d, e close brace$ are surjective?

There are $4 to the power 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 to the power 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 to the power 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 to the power 5$ function. There are $(\binom{4}{1})$ groups of functions excluding a single element, $(\binom{4}{2})$ groups of functions excluding a pair of elements, and $(\binom{4}{3})$ groups of functions excluding a triple of elements. This means that the number of functions which are not surjective is:
$(\binom{4}{1}) 3^{5} - (\binom{4}{2}) 2^{5} + (\binom{4}{3}) 1^{5}$
. We can now say that the number of functions which are surjective is:
$4^{5} - [(\binom{4}{1}) 3^{5} - (\binom{4}{2}) 2^{5} + (\binom{4}{3}) 1^{5}]$
.
The number of surjective functions is:
$5^{5} - [(\binom{5}{1}) 4^{5} - (\binom{5}{2}) 3^{5} + (\binom{5}{3}) 2^{5} - (\binom{5}{4}) 1^{5}]$
. We took the total number of functions $5 to the power 5$ and subtracted all that were not surjective. There were $(\binom{5}{1})$ ways to select a single element from the codomain to exclude from the range, and for each there were $4 to the power 5$ functions. But this double counts, so we use PIE and subtract functions excluding two elements from the range: there are $(\binom{5}{2})$ choices for the two elements to exclude, and for each pair, $3 to the power 5$ functions. This takes out too many functions, so we add back in functions which exclude 3 elements from the range: $(\binom{5}{3})$ choices for which three to exclude, and then $2 to the power 5$ functions for each choice of elements. Finally we take back out the 1 function which excludes 4 elements for each of the $(\binom{5}{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 !$ . This might seem like an amazing coincidence until you realize that every surjective function $f : X \to Y$ with $| X | = | Y |$ finite must necessarily be a bijection. The number of bijections is always $| X |!$ in this case. What we have here is a combinatorial proof of the following identity:
$n^{n} - [(\binom{n}{1}) (n - 1)^{n} - (\binom{n}{2}) (n - 2)^{n} + \dots + (\binom{n}{n - 1}) 1^{n}] = n!$
.

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$ ? How many contain no repeated letters?

By now it should be no surprise that there are $8 to the power 5$ words, and $P open parenthesis 8, 5 close parenthesis$ 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 $open brace 1, 2, and so on, 5 close brace$ to ${a, b, \dots, h}$ . 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 $vertical bar A vertical bar equals 5$ and $vertical bar B vertical bar equals 8$ , then the number of functions $f : A \to B$ is $8 to the power 5$ and the number of injections is $P open parenthesis 8, 5 close parenthesis$ . 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 $open brace 1, 2, and so on, 9 close brace$ ? How many 9-bit strings are there (of any weight)?

We saw in Binomial Coefficients that the answer to both these questions is $2 to the power 9$ , 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 to the power 9$ also looks like the answer you get from counting functions. In fact, if you count all functions $f : A \to B$ with $vertical bar A vertical bar equals 9$ and $vertical bar B vertical bar equals 2$ , this is exactly what you get.

This makes sense! Let $A equals open brace 1, 2, and so on, 9 close brace$ and $B = {y, n}$ . 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 $open brace 0, 1 close brace$ 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 $(\binom{9}{3})$ and $P open parenthesis 9, 3 close parenthesis$ . We do have a function model for $P open parenthesis 9, 3 close parenthesis$ . This is the number of injective functions from a set of size 3 (say $open brace 1, 2, 3 close brace$ to a set of size 9 (say $open brace 1, 2, and so on, 9 close brace$ ) 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:

$f (1) = 5 f (2) = 8 f (3) = 4$

This is a different function from:

$f (1) = 4 f (2) = 5 f (3) = 8$

Now $P open parenthesis 9, 3 close parenthesis$ counts these as different outcomes correctly, but $(\binom{9}{3})$ will count these (among others) as just one outcome. In fact, in terms of functions $(\binom{9}{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.¹

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.

After another gym class you are tasked with putting the 14 identical dodgeballs away into 5 bins. This time, no bin can hold more than 6 balls. How many ways can you clean up?

_____

$(\binom{18}{4}) - [(\binom{5}{1}) (\binom{11}{4}) - (\binom{5}{2}) (\binom{4}{4})]$ .

Based on the previous question, give a combinatorial proof for the identity:

$(\binom{n}{k}) = (\binom{n + k - 1}{k}) - \sum_{j = 1}^{n} (- 1)^{j + 1} (\binom{n}{j}) (\binom{n + k - (2 j + 1)}{k - 2 j})$

Illustrate how the counting of derangements works by writing all permutations of $open brace 1, 2, 3, 4 close brace$ and the crossing out those which are not derangements. Keep track of the permutations you cross out more than once, using PIE.

The 9 derangements are: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.

Let $d_{n}$ be the number of derangements of $n$ objects. For example, using the techniques of this section, we find

$d_{3} = 3! - ((\binom{3}{1}) 2! - (\binom{3}{2}) 1! + (\binom{3}{3}) 0!)$

. We can use the formula for $(\binom{n}{k})$ to write this all in terms of factorials. After simplifying, for $d sub 3$ we would get

$d_{3} = 3! (1 - \frac{1}{1} + \frac{1}{2} - \frac{1}{6})$

. Generalize this to find a nicer formula for $d_{n}$ . Bonus: For large $n$ , approximately what fraction of all permutations are derangements? Use your knowledge of Taylor series from calculus.

Discrete Mathematics: An Open Introduction, 3rd edition, by Oscar Levin (discrete.openmathbooks.org), licensed under CC BY-SA 4.0; this adaptation is distributed under the same license. License: CC-BY-SA-4.0.