Enumerative combinatorics is founded on the three principles that I mentioned in the previous
video. This video is to explore these principles in detail. Even if you are familiar with combinatorics,
this video will revisit those concepts very clearly, so it will be worth your time.
Addition principle is to come up with different distinct approaches to solve the same task.
You either choose the first approach, or the second one, or the nth one, and only one of
them. We now denote the number of ways to do the task using the first approach as a_1,
the second approach as a_2, all the way to a_n. The addition principle tells us that
we need to add these numbers up to get the total number of ways to achieve the big task.
The multiplication principle is to break the big task into different subtasks. You have
to go through the first subtask, second subtask, all the way to the nth one, and all needs
to be done. We now denote the number of ways to do first subtask as b_1, the second subtask
as b_2, all the way to b_n. The multiplication principle tells us that we need to multiply
these numbers up to get the total number of ways to achieve the big task.
The inclusion-exclusion principle is pretty similar to the situation of the addition principle
where you need to choose one approach out of many. However, the approaches are not distinct;
there could be overlapping areas. This is because there could be some ways that can
be classified under different approaches. We use a_(1,2) to denote the number of ways
in the overlapping area. Then we need to subtract a_(1,2) to offset the overlapping area. Of
course, we also have the overlapping area between the first and third approach, and
so on. However, for those that can be classified under the first, second and third approach,
the subtracting overshoots. Therefore, we need to add it back, and the process continues.
This is the inclusion-exclusion principle.
Suppose you are planning a trip from A to B. There are also places C and D where you
might want to have a transfer at. Then this diagram shows all the different possible routes
you can take, where different colour represents different airlines. It is not as complicated
as it seems. We can simplify the diagram by only recording the number of flights available
from a point to the other. So the problem of flying from A to B can be done in the following
approaches: Direct flight, through C, and through D Because you only take one of the
approaches, we use the addition principle. If we know the number of ways to do the task
using each of the approaches, we just add them up to get the final answer. Looking back
at our schematic diagram, there is only 1 direct flight available. So the number of
ways to use the first approach is 1. For the second approach, we have two subtasks to do.
We need to first go from A to C, and then from C to B. Both subtasks need to be done
to count as the second approach, so we need to use the multiplication principle. Going
back to the diagram, From A to C we have two flights, from C to B we have three flights.
So we have 2 and 3 in the corresponding positions. and we can put the product in the second approach.
Now, we can do the same thing for the third approach. Then this expression is the total
number of ways to arrange a flight from A to B. This is an example of using addition
and multiplication principle.
Along the lines of planning a trip, let’s pretend we are planning where the destination
should be. Suppose we want to go there by direct flight, and there are 3 airlines that
operate flights from our city. Airline A can fly you to 75 different destinations, Airline
B can fly you to 27 different destinations, while Airline C carries you to 39 different
destinations. To calculate how many destinations you can go, it is important to note that you
only choose 1 airline for your trip, which makes the problem able to be dealt with by
the addition principle. However, there are some destinations which are very popular,
and two or more airlines operate flights to there. We have double-counted these destinations
when we simply add the numbers up, so we need to use the inclusion-exclusion principle instead.
That means, after we add these numbers up, we need to subtract the number of destinations
where two of the airlines operate flights to. Let’s say these are the number of destinations
where any pair of airlines go to. Then we need to subtract these numbers. Finally, of
course, there are really popular destinations where all three airlines operate flights to,
and there are 5 of them. So we add back 5, and we can then calculate the result. This
is an illustration of the inclusion-exclusion principle. You might be a little surprised
that I didn’t use Venn diagram to explain this principle, because first of all, drawing
a Venn diagram for four or more circles is not easy. Another reason is simply that it
does not aid understanding too much. You need to understand that the number of destinations
that airline A operates flights to is represented by this entire circle instead of only this
region. So while Venn diagram is a visually appealing diagrammatic representation of what
we are doing, I don’t really like using it to make sense of what is happening.
While we’re at it, we could also see what permutation and combination are. They are
not something new, but just some more sophisticated tools that can be derived from the multiplication
principle, which we have seen earlier. Permutation and combination concern these situations,
where there are n different elements. You need to choose r of them. For example, this
will be one possible choice. However, permutation and combination differs in whether changing
the order of choice counts as different. For permutation, these two choices would be counted
as different, while for combination, they would be counted as the same thing. Permutation,
usually denoted as nPr, could be calculated as the product of n, n-1, and so on until
n-r+1. This is because the first position has n choices, the second position has (n-1)
choices because one element has already been chosen. This process continues for all the
r positions we have. So we end on (n-r+1). The reason we use multiplication is that we
have to perform all the subtasks of choosing an object in a position. For combination,
we denote a little differently: n choose r. The only difference between combination and
permutation is whether we count these different orderings the same. For each choice of r objects,
the number of ways to move it around is exactly rPr. If we multiply the number of choices
we have by the number of ways to order those r objects, we should get back nPr.
Okay, so we have the permutation nPr formula, as well as the n choose r formula. We can
now substitute the explicit formula of rPr and nPr in the first formula into the second
formula. So we have this explicit formula of n choose r as well. These formulae are
rarely seen because writing these out is annoying. In order to write less, we denote n factorial
to be the product of the first n numbers. Why is this useful? Multiply the first formula
by (n-r)! on both numerator and denominator. The numerator amounts to n multiplying all
the way to 1, so it is n factorial, and so we can write the permutation like this, which
is much easier than writing the entire product out. The same thing can be done to the combination
formula. The numerator can also be rewritten as n factorial, In addition, this part of
the denominator can also be rewritten as r factorial. So we have a simplified formula
for n choose r. And so, we have constructed some more sophisticated tools based on one
of the founding principles - the multiplication principle, with these formula we derived.
In the next video, we will focus on this particular scenario mentioned in the introductory video.
What I haven’t mentioned is that swapping two people borrowing money is counted the
same, and swapping two people depositing money is also counted the same way of queuing these
customers up. This video should make clear why whether swapping matters, matters. So
you can try to solve this problem until the next video, where I reveal how to come up
with the solution.
If you enjoyed this video, give it a thumbs up and share it. Don’t forget to subscribe
with notifications on, so you don’t miss out any new videos in this series. See you
in the next video. Bye!