In the previous videos, I said we would tackle this particular case in this video. Remember
that A represents the number of people depositing money, B the amount of deposit, C the number
of people borrowing money, D the amount of loan, and E the amount of cash the bank initially
has. This set of conditions can then be interpreted as follows: A=C meaning that the numbers of
people depositing and borrowing are the same, while B=D means that the amount of deposit
and loan are the same. The bank originally does not have any cash. Under this scenario,
the exact amount of money does not matter as long as it is the same. All we need to
ensure is that the number of people depositing money is at least the number of people borrowing
money at every point of the queue. All that means is that there is actually only one variable
affecting the number of ways of queuing. Let’s call it n. Then denote the number of ways
to queue up the customers to be C with subscript n. This is because this class of numbers is
called the Catalan numbers, named after well, Catalan, a French-Belgian mathematician.
We know that C_n has to depend on n, and so it is a function of n, where n is a nonnegative
integer. The point is to find the function. Specifically, expressing it analytically.
In other words, expressing explicitly in terms of a finite combination of other recognizable
functions. Finding the function analytically is sometimes not doable. An algebraic example
would be to let f of n to be the smallest positive root of an equation. If you want
a combinatorial example, let the function to be R(n,n). In the world of combinatorics,
this can mean at least two different things: Ramsey number, or the number of self-avoiding
walks in an n times n grid. There are links in the description explaining what those terms
mean if you are interested. Luckily, the problem is somehow simple enough to have an analytic
form, which we are going to derive.
An important realization is that who you put in the front, can affect who you can put in
the back. This realization might make you want to try using the tree diagram to analyse
the entire situation. To avoid taking up too much space, we use a blue upper branch to
denote that the next person is borrowing money, while a green lower branch is used to denote
that the next person is depositing money. From what we discussed, the number of green
branches should be at least the number of blue branches at any point of drawing the
diagram. The bank does not have any cash, so the first person has to be depositing money.
Even if there is only 1 branch, we also draw it in our tree diagram for consistency. The
next person can be either depositing or borrowing money, so we have two possible branches here.
If there are only 2 customers, then this white path shows the only possibility, that the
first one deposits, and the second borrows. If there are more customers, we can move on.
For the upper branch, the next customer has to be depositing money because the bank now
does not have any cash. For the lower branch, we can have two branches, because in these
two cases, the number of green branches still exceeds that of blue ones. Notice that we
have a junction here. These two paths are of course different, and they represent different
ways to queue up the customers, but they have something in common: there are two green branches,
and 1 blue branch each. And by utilizing a tree diagram, we show that there are only
2 ways of queuing the customers up, if there are 2 depositing and 1 borrowing, which are
shown by these two different paths. And this is true for all junctions that we can draw:
The number of paths leading to a particular junction equals the number of ways of queuing
up the customers of a certain configuration, that is, a fixed number depositing and a fixed
number borrowing. And again, if we move on from the junction, then we can have whoever
to queue up after that, because the number of green branches will have to be at least
that of the blue ones no matter what. And we can continue this process forever.
From what we see, it seems that there is a hidden horizontal line that does two things:
barring any paths from crossing the it, as well as containing the points that are the
destinations of the paths. That is because the line contains points where the number
of green branches and that of the blue ones up to that point equals, which is what we
are caring about. So C_n can also be formulated as the number of paths to the nth point on
the line (except for the first one), like C_1 corresponds to this point, C_2 corresponds
to this point, and C_3 corresponds to this point and so on. Finally, let’s rotate all
these counter-clockwise by 45 degrees. Then the paths going from the bottom left to the
points on the white line are called Dyck paths. The question then becomes how many Dyck paths
are there for a given point on the white line. The reason we turn the original problem into
this one is that it is much easier to visualize than manipulating the queues. But then how
do we solve this problem then?
In this video, we are presenting one of the many solutions, and some of the other solutions
will be presented in the next video. The reason why there are so many solutions is that there
are many combinatorial interpretations giving Catalan numbers, including the triangulation
of a polygon, and some solutions make sense in some interpretations, but don’t in other;
and some solutions do the opposite.
It’s worth reiterating the reformulation of the problem. We want a path from the bottom
left to the top right. We can only travel in two directions: up and right. One more
restriction is that the path cannot go above the diagonal line, and we want to find the
number of paths available. To solve this problem, let’s tackle an easier case and drop the
restriction of the diagonal. There are n steps in each of the directions in order to get
to your destination. If we forget the visualization for a moment, and treat all the different
paths as a sequence of ups and rights, then it is easy to see that out of those 2n steps,
we have to choose n slots to put the rightward steps. The other slots would automatically
be the upward steps, and so there are in total 2n choose n number of ways to go from the
bottom left to the top right without the diagonal restriction.
But of course this isn’t C_n. Among those 2n choose n paths, there are of course some
good ones, but there also includes some bad ones. So in the calculation of C_n, we need
to subtract the number of bad paths from 2n choose n. But of course, we need to see how
to calculate the number of bad paths.
So we see a bigger picture. We add one row at the top. We also start off with (0,0),
and end at (n,n), and this does not change. For any bad paths like this one, it has to
touch or cross over this orange line at least once. We consider this part of the path after
touching the orange line, and reflect across the line. The thing about this method is that
we can always reflect back to where we started, so we have established something called a
one-to-one correspondence, or a bijection if you want some mathematical jargon. That
means, the number of bad paths equals the number of reflected paths. It seems silly
to write out, but it allows us to focus on counting the no. of reflected paths. Now,
since the endpoint of the original path is at (n,n), the endpoint of the reflected path
should be at (n-1, n+1). If we again take a more systematic look at the whole situation,
where we view a path as a sequence of ups and rights like this, then we have again 2n
steps because what we have done is reflection, and the number of steps should not change.
But we have (n-1) slots for the rights only. This is because the x-coordinate of the endpoint
is (n-1). So now, the number of bad paths is exactly, 2n choose (n-1).
In summary, C_n equals the number of both good and bad paths, which is 2n choose n,
subtracting the number of bad paths, which is 2n choose (n-1). Some people would have
an algebraic treatment to that and figure out that it is a fraction of the binomial
coefficient. In one of the other derivations of algebraic forms of Catalan numbers, we
will attempt to explain more naturally where the 1 over (n+1) comes from.
If you enjoyed this video, give it a thumbs up and share it. Don’t forget to also subscribe
with notifications on so that you get notified when a new video comes up. See you in the
next video. Bye!