Combinatorics is a very rich field of mathematics, from very classical enumerative ones, to using
analysis on traditional combinatorics, as well as some seemingly unrelated fields, like
graph theory, and the famous splitting necklace problem. This video series only focuses on
the enumerative part of it. It is somewhat synonymous with systematic counting, but being
systematic is not as easy as one might think, as we will show later.
The amazing thing about this part of combinatorics is that there are only 3 principles that found
the entire thing, including addition, multiplication, and inclusion-exclusion. Throughout this video
series, we would rarely use any tools based on inclusion-exclusion principle, but for
the sake of completeness, I would also include it in the series. Some might remember permutation
and combination as a symbol for combinatorics, but they are tools based off of the multiplication
principle. So the founding principles are really just these three.
The entire video series builds on one general scenario. Let’s say we are at a bank, and
people are queuing up, either to deposit money, denoted in green, or to borrow money, denoted
in blue. Suppose all transactions are done in cash. If the bank does not have enough
cash to lend, the transaction is not successful. There are A number of people, each of whom
deposits B dollars. On the other hand, C number of people all want to borrow D dollars. The
bank originally has only E dollars of cash. Your job is to arrange these customers in
a queue so that every transaction is successful. That means, if at some point, the bank does
not have any cash, the next person in line cannot be borrowing money. You should have
prevented it from happening in the first place. The question is under these constraints, how
many ways there are to queue up these customers.
There is something to note: the amount of money that the bank has after all those transactions
is independent of the arrangement of the customers, and the balance is given by AB+E-CD, where
AB+E is the amount gained, and CD is the amount lost. This balance has to be nonnegative.
Otherwise, no matter how you arrange the customers, you can never make all transactions successful.
As far as I know, the problem of how many ways there are to queue up the customers with
so many variables is still unsolved. This shows how counting systematically can be difficult,
and in this case, extremely difficult. However, if we have some constraints on the variables,
like this one, then the problem can be solved. In fact, this particular constraint is the
situation that we will discuss in the video after the next one. You might want to try
the problem under this constraint before I reveal the solution later on in the series.
Originally, I wanted to have a crash course in combinatorics in this video, but it turns
out this introductory video would then be too long. I would put it in the next video
though. This is because I have previously asked viewers to fill in the Google form,
linked in the description, which tells me that not all of you know combinatorics, so
I need to make a crash course in combinatorics so that we are all on the same page. It would
be helpful if more of you can fill in the form so that I know more of your math levels
to adjust whether I should talk briefly and deeply about the background knowledge required
for the content of the video.
If you enjoyed this video, give it a thumbs up, and share this video. Subscribe to Mathemaniac
with notifications on so that you can be notified when I upload a new video in this series.
See you in the next video. Bye!