maths.free › Combinatorics & Graph Theory › 4. Counting › Advanced Counting Using PIE

Advanced Counting Using PIE

Investigation 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?

Section Preview

Investigation

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?

Sticks and stones allows us to count the number of ways to distribute 10 cookies to 3 kids and natural number solutions to \(x+y+z = 10\), 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\). This was done by first assigning each kid (or variable) 2 cookies (or units) and then distributing the rest using sticks and stones.

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\). It turns out this is considerably harder.

Notice that if we consider the complementary event, i.e., distributions of cookies in which kids do get more than 4 cookies, then we are back to a sticks and stones problem with a lower bound. If we could count this, then subtracting from the total number of distributions should give us the desired answer. However, the problem is that the complement of no kid gets more than 4 cookies is at least one kid gets more than 4 cookies. We know how to take care of requiring all kids getting at least 4 cookies, but how do we handle the case where one or more kids get at least 4 cookies? We must use PIE.

PIE for Multisets

The Principle of Inclusion/Exclusion (PIE) gives a method for finding the cardinality of the union of not necessarily disjoint sets. We saw in 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 that are in all three sets once too often, so we need to add it back in. In terms of the 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

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}\), using 11 stones and 2 sticks (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| = {8 \choose 2}\)
  • \(|B| = {8 \choose 2}\)
  • \(|C| = {8 \choose 2}\)
  • \(|A \cap B| = {3 \choose 2}\)
  • \(|A \cap C| = {3 \choose 2}\)
  • \(|B \cap C| = {3 \choose 2}\)
  • \(|A \cap B \cap C| = 0\)

Combining all of these we see \[|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\].

Thus the answer to the original question is \({13 \choose 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!

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

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Counting Derangements

Investigation

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 sticks and stones. 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\}\): \[123 ~~ 132 ~~ 213 ~~ 231 ~~ 312 ~~ 321\]. 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 \text{ 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 that are not derangements, you will be left with just 9 derangements. Let's see how we can get that number using PIE.

Example

How many derangements are there of 4 elements?

Solution

We count all permutations and subtract those that 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 that 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 that 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: \[4! - \left[{4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4}0!\right] = 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:

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Counting Functions

Investigation

  1. Consider all functions \(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\). How many functions are there in total? How many of those are injective? Remember, a function is an injection if every input goes to a different output.

  2. Consider all functions \(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\). 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: \[5! - \left[ {5\choose 1}4! - {5 \choose 2}3! + {5\choose 3}2! - {5 \choose 4}1! + {5\choose 5}0! \right]\].

    Explain why this is correct.

  3. 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!

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.

In we saw how to count all functions (using the multiplicative principle) and in 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 that 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

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

Solution

There are \(2^5\) functions total, two choices for where to send each of the 5 elements of the domain. Now of these, the functions that 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 overcount these. It's PIE time!

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 is an example of counting functions!

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (3)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Based on the previous question, give a combinatorial proof for the identity: \[{n \choose k} = {n+k-1 \choose k} - \sum_{j=1}^n (-1)^{j+1}{n \choose j}{n+k-(2j+1) \choose k - 2j}\].

  2. Illustrate how the counting of derangements works by writing all permutations of \(\{1,2,3,4\}\) and then 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.

  3. Let \(d_n\) be the number of derangements of \(n\) objects. For example, using the techniques of this section, we find \[d_3 = 3!-\left({3 \choose 1}2! - {3 \choose 2}1! + {3 \choose 3}0! \right)\]. We can use the formula for \({n \choose k}\) to write this all in terms of factorials. After simplifying, for \(d_3\) we would get \[d_3 = 3!\left(1 - \frac{1}{1} + \frac{1}{2} - \frac{1}{6} \right)\]. 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.

Symbols used here

\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
i
imaginary unit
i² = −1.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
\neq
not equal
The two sides are different.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

How to: Advanced Counting Using PIE

  1. Apply the principle of inclusion/exclusion to solve counting problems involving multisets with bounded multiplicity.
  2. Apply the principle of inclusion/exclusion to solve counting problems involving derangements.
  3. Apply the principle of inclusion/exclusion to solve counting problems involving surjective functions.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

あなた自身を試してみてください

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

ここに Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs