So far we have seen the solution of this particular case, where there is actually only one variable,
and the solution is the Catalan numbers, where the argument n depends on the number of customers.
However, we want to generalize a bit, namely loosening one particular constraint about
the number of people depositing and borrowing money. Then, the solution depends on both
the value of A and C, but I write that as C with subscripts A-C and C instead. Notice
that C_(0,n) is the same as C_n.
We go back to the grid again, which is the tilted tree diagram we used to analyze the
scenario. Any path leading to a particular point corresponds to a particular case of
A and C, and in this case, corresponding to 4 depositing money and 2 borrowing money,
which means that the number of paths to this yellow point is C with subscript 2 and 2.
Here, the first two represents the difference between the number of people depositing and
borrowing, while the second 2 is the number of people borrowing money. What you can think
of using this notation is that the first number tells you which diagonal from the main one,
and the second number tells you which entry on the diagonal. Can we express this in terms
of other similar C something? Let’s consider this green point. The last step going to the
green dot must be from either this orange dot, or the yellow dot. So that means, the
number of paths to the green dot, which is denoted as C_(1,3) is equal to C_(0,3), which
is the number of paths to the orange dot; plus C_(2,2), the number of paths to the yellow
dot. By rearranging, we can express C_(2,2) in terms of numbers on the previous diagonals.
More generally, we have this recurrence relation. There are two base cases we need to consider
before using the recurrence relation. The first one is C_(0,k). This just corresponds
to paths leading up to points on the red main diagonal, which is just the Catalan numbers
themselves. Now, consider the paths leading up to the red dot on the main diagonal. All
paths have to pass through the green dot, so C_(1,n) are also Catalan numbers, just
shifted by one place.
With these three relations, we can already find all the values of C_(n,k) by repeatedly
applying this powerful recurrence relation. We are now going to use this recurrence relation
to try to guess the formula of C_(n,k) only in terms of n and k. To do that, we first
write out the formula for C_(0,k) and C_(1,k) in terms of factorials only. Then by using
the recurrence relation, we can obtain C_(2,n). Now, by simply substituting n=2 into the recurrence
relation, we obtain this formula, then by substituting the formula in, we can then do
some algebra. Now we can do the same thing to obtain C_(3,k). You might have already
spot the pattern, but there is no harm in doing one more. Now, C_(4,k) looks like this,
which should confirm your belief in the pattern. So now, the general form of C_(n,k) can be
found using this general formula. And in fact, you can check that this formula also holds
for n = 0 and 1. Of course we can’t say this is a logical proof, so we can use mathematical
induction to make these all valid.
Now we have generalized the Catalan numbers of only one variable n, to another class of
numbers with two variables, by loosening the constraint that A must equal to C. It is also
possible to generalize in another direction, by considering the original amount of cash
that the bank has is not necessarily 0, or even considering both generalizations at the
same time. You can see how the grids change when you generalize these conditions. All
these scenarios have known formula for the number of ways of queuing up the customers.
However, notice that in all these generalized cases, we don’t change the condition about
the deposit and loan amount, and in fact it would be very tedious if we consider B not
equal to D.
The next video is going to be a personal anecdote on how this video series came about, because
this project actually meant something to me. It will be very different from what I usually
do, but I hope you will enjoy the next video.
If you enjoyed this video, don’t forget to like and share this video, and subscribe
to the channel with notifications on. Stay tuned for the next video! See you next time.