Proof on Catalan numbers

865 Views Asked by At

In the book I'm using on Catalan numbers, the author gives a scenario in order to develop the formula for Catalan numbers.

The scenario is that a boy has an empty jar. Every day he either puts in a dollar coin or takes on out for $2n$ days. At the end of the $2n$ days, the jar is empty. In how many ways can this happen?

I understand how he gets to the Catalan numbers. But there is one part where he says this:

note that if $n\gt 0$ then there had to be a first day other than the starting day when the jar was empty.

I'm having trouble understanding why this is the case. When I think of taking or putting a coin in a jar as the equality $y=x$, you could just add a coin in for the first $n$ days, then take one out for the remaining $2n - n = n$ days.

Why does there have to be a day other than the starting day in which the jar was $0$?

2

There are 2 best solutions below

1
On BEST ANSWER

The "first day other than the starting day when the jar was empty" can also be the last day, as it is in your example. That must be the case if $n=1$, for example: since there are only two days, he has to put a coin in the first day and take it out the second.

0
On

The jar has always $\ge 0$ dollars in it. It starts out empty, and ends up empty. It could be empty in before the end (say you put money in for 3 straigt days, take out money for 3 straight days, and then continue your merry way for the rest of the month). It doesn't have to be empty in between. Methinks you got those two cases mixed up?